Programmer's Blog

Programmer's reference

[C++] Basic Binary Search Tree

struct node
{
   int data;
   node * left;
   node * right;
};

//insert elements
node * insert(node * root, int value) {
 
   node *newnode = new node();
   newnode->data = value;
 
   if (!root)
   {
     newnode->left = newnode->right = NULL;
     return newnode;
   } 
   else
   {
     node *tmp = root;
     while (tmp->left != NULL || tmp->right != NULL)
     {
         if (value <= tmp->data)
         tmp = tmp->left;
         else if (value > tmp->data)
         tmp = tmp->right; 
     }
     if (tmp->left) tmp->right = newnode;
     else tmp->left = newnode;
 }

 return root;
}

//inorder search
void inOrder(node *root) {

  if (!root) return;
  if(root->left) inOrder(root->left);
      cout << root->data << " ";
  if(root->right) inOrder(root->right);
}

int max(int i , int j)
{
   return i > j ? i : j;
}

//retrieve height of BST
int height(Node* root)
{
 
  if (!root) return 0;
  else if (!root->left && !root->right) return 0;
  int i = height(root->left) +1;
  int j = height(root->right) +1;
  return max(i,j);
 
}

//Level Order Search
void printLevel(node* root, int h)
{
  if (!root) return;
  if (h == 1)
    cout << root->data << " ";
  else if (h > 1)
  {
     printLevel(root->left, h - 1);
     printLevel(root->right, h - 1);
  }
}

void printLevelOrder(node * root)
{
  if (!root) return;
  int h = height(root);
  for (int i = 0 ; i <= h ; i++)
     printLevel(root, i);
}

//lowest common ancestor
node * lca(node * root, int v1, int v2)
{
   if (!root) return NULL;
 
   if (root->data == v1 || root->data == v2)
       return root;
 
   node* lcaLeft = lca(root->left, v1, v2);
   node* lcaRight = lca(root->right, v1, v2);
 
   if (lcaLeft && lcaRight) return root;
       return (!lcaLeft) ? lcaRight : lcaLeft;
 
}


bool processBST(Node* root, int& min, int& max)
 {
   if (!root) return true;
 
   if(root->data > min && root->data < max &&
     processBST(root->left, min, root->data) && processBST(root->right, root->data, max))
   return true;
     else
   return false;
 
 }

//check if a tree is BST
bool checkBST(Node* root) {
 
 if (!root) return true;
 
 int min = -2147483648;
 int max = 2147483647;
 
 bool a = processBST(root, min, max);
 return a;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: