Tree & Binary Search Tree

[greeksforgreeks] A program to check if a binary tree is BST or not.

The following are the best solution greeksforgreeks provided.

Solution 1:

  Using in order traversal, and store the result in a auxiliary three element array, if the array is sorted in ascending order, the tree is BST.
  or we can optimization the space like:

[code]
bool isBST(Node *root)
{
     static struct Node *prev = NULL;
     if (root)
     {
         if(!isBST(root->left))
             return false;
         if ( prev != NULL && root->value <= prev->value)
             return false;
         prev = root;
         return isBST(root->right);
     }
     return true;

}

Find lowest common ancestor of two nodes in a binary tree.

Solution:

    Need to implement a helper function which find if a node is a child of the root node.

[code]

bool Has(Node *r, Node *p)
{
    if (r == NULL) return false;
    if (r == p) return true;
    return Has(r->left, p) || Has(r->right, p);
}

Node *LCA(Node *r, Node *p, Node *q)
{
    if (Has(r->left, p) && Has(r->left, q)) 
       return LCA(r->left, p, q);
    if (Has(r->right, p) && Has(r->right, q))
       return LCA(r-right, p, q);
    return r;
}

Find level of a node in a binary tree.

Solution:

[code]
int  findLevel(Node *r, Node *p, int level)
{
    if (root == NULL)
        return -1;
    if ( root == p ) return level;

    int ll = findLevel(root->left, p, level+1);
    if (ll != -1)  return ll;
    return findLevel(root->right, p, level+1);
}

Find Distance between two nodes in a binary tree.

Solution:
   formula: Dist(p,q) = Dist(r,p) + Dist(r,q) - 2*Dist(r, lca)

[Code] 
int Distance(Node *r, Node *p, Node *q) 
{ 
    Node *lc = LCA(r, p, q);
    int Distrp = findLevel(r, p, 0);
    int Distrq = findLevel(r, q, 0);
    int Distlca = findLevel(r, lc, 0);
    return Dist(r, p) + Dist(r, q) - 2* Dist(r, lc);
}

Binary tree iterative pre-order traversal.

Solution:

    using a auxiliary stack

[Code]
void Preorder(Node *r)
{
    stack<Node*>s;
    Node *c;
    s.push(r);
    while(!s.empty()) {
       Node *t = s.top();
       // print out the value of the Node
       cout << t->value << endl;
       s.pop();
       if(t->right) s.push(t->right);
       if(t->left) s.push(t->left);
    }
}

Binary tree iterative post-order traversal.

Solution:
    using two auxiliary stacks

[Code]

void Postorder(Node *r)
{
    Node *c;
    stack<Node*>s;
    stack<Node*>output;
    s.push(r);
    while(!s.empty()) {
       Node *t = s.top();
       output.push(t);
       s.pop();
       if(t->left) s.push(t->left);
       if(t->right) s.push(t->right);
    }
    while(!output.empty()) {
       cout << output.top()->value << endl;
       output.pop();
    }
}

Binary tree iterative in-order traversal.

Solution:
     using one auxiliary stack.
       

[code]
void Inorder(Node *r)
{
    Node *c = r;
    stack<Node *> s;
    while(1) {
      if(c) {
         s.push(c);
         c = c->left;
      }
      else{
         if (s.empty()) break;
         c = s.top();
         cout << c->value << endl;
         s.pop();
         c = c->right;
      }
    }
}

Traverse a binary tree level by level.

Solution:

    1. find the max height of the tree;

    2. print the tree level indexed by the level index;

[code]
int TreeHeight( Node *r)
{
    if (r == NULL) return 0;
    return max(TreeHeight(r->left), TreeHeight(r->right)) + 1; 
}

void printLevel(Node *r, int level)
{
     if (r==NULL) return;
     if ( level <0 ) return;
     if (level == 0)
          cout << r->value <<endl;
     printLevel(r->left, level - 1);
     printLevel(r->right, level - 1);
}

Find number of leaves in a binary tree.

Solution1:

[code]
int findLeaves(Node *r)
{
    if (r == NULL) return 0;
    if (r -> left == NULL && r->right == NULL) return 1; 
    return findLeaves(r->left) + findLeaves(r->right); 
}

Solution2: using static variable

[code]
int findLeaves(Node *r)
{
    static int count = 0;
    if (r == NULL) return count;
    if (r -> left == NULL && r->right == NULL) count ++; 
    return findLeaves(r->left) + findLeaves(r->right); 
}

Clone a binary tree

Solution: using recursive method;

[code]

struct Node {
      int value;
      Node *left;
      Node *right;
};
    
Node *cloneBinaryTree(Node *r)
{
    if (r==NULL) return NULL;
    Node *p = new Node;
    p->value = r->value;
    p->left = cloneBinaryTree(r->left);
    p->right = cloneBinaryTree(r->right);
    return p;
}