bst_whiteboarding.cpp

// - function makes a binary search tree from an array
// - traverse the tree from left to right

#include <iostream>
#include <vector>

template<typename T=int>
struct Node {
  Node* left;
  Node* right;
  T val;

  Node(): left(nullptr), right(nullptr), val(0) {};
  Node(T x): left(nullptr), right(nullptr), val(x) {};
};


// {4,6,2,1,3,3,7,2}

//       4
//      /  \
//     2    6
//    / \    \
//   1   3    7
//      / \
//     2   3


template<typename T=int>
void traverse_tree(Node<T>* root_node){
    if(root_node == nullptr){
        return;
    }

    std::cout << root_node->val << "\n";
    traverse_tree(root_node->left);
    traverse_tree(root_node->right);
}

template<typename T=int>
Node<T>* add_val_to_tree(Node<T>* root_node, T val){
    Node<T>* node = new Node<T>(val);

    if(root_node == nullptr){
        return node;
    }

    Node<T>** node_ptr = &root_node;
    while(*node_ptr != nullptr){
        if(val <= (*node_ptr)->val){
           node_ptr = &(*node_ptr)->left;
        }
        else{
           node_ptr = &(*node_ptr)->right;
        }
    }
    *node_ptr = node;
    return root_node;
}

// will make an unbalanced BST of time complexity O(nlogn)
Node<int>* get_tree_from_array(const std::vector<int>& values){
   Node<int>* root_node = nullptr;

   // O(n)
   for(int i=0;i<values.size();++i){
       // insert = O(logn)
       root_node = add_val_to_tree(root_node, values[i]);
   }
   return root_node;
}


int main(){
  auto root = get_tree_from_array(std::vector<int>{10,1,4,9,1,2,7,3});
  traverse_tree(root);

  return 0;
}