Problem:
 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes   Create an algorithm to decide if T2 is a subtree of T1
Solution:

1. Traverse the Tree T1.
2. For each node, call a method to do the following (Step 3),
3. traverse both the Tree T1 and T2, until tree T2 exhausts or until data of T1 and T2 does not match. 
4. Return true if T2 is a subtree of T1 else return false.

 

 Complexity: O(m*n) in the worst case
Code:

Binary Search Trees

35-bst

Get Level of a node in a Binary Tree

Given a Binary Tree and a key, write a function that returns level of the key.
For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0.

Solution:
             While calling left sub tree or right sub tree increment the level by 1. When the Key is found return the current level.

Complexity:   O(n), where n is the number of nodes.

Code:

int getNodeL(Tnode *root, int key, int level) {
    

    int leftlevel = 0, rightlevel = 0;
    
    if (root == NULL)
        return 0;
    
    if (key == root->data)
        return level;
    
    leftlevel = getNodeL(root->left, key, level + 1);
    
    if (leftlevel == 0)
        rightlevel = getNodeL(root->right, key, level + 1);
    
    return leftlevel + rightlevel;
}

Print Ancestors of a given node in Binary Tree

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
For example, if the given tree is following Binary Tree and key is 7, then your function should print 4, 2 and 1.

              1
            /   \
          2      3
        /  \
      4     5
     /
    7

Solution: 

Traverse the tree recursively until the key is found, 

start printing the data in the nodes as the recursive call 

returns.

Complexity: O(n), where n is the no of nodes.

Code: 

int printAncestor(Tnode *root,int key)
{
    if(root==NULL)
        return 0;
    if(key==root->data)
        return 1;
    if(printAncestor(root->left, key) ||
            printAncestor(root->right, key))
    {
        printf(" %d ",root->data);
        return 1;
    }
    return 0;
}

Print BST keys in the given range

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

Solution:
              Do inorder traversal, if current nodes' data is between K1 and K2 (K1<= root->data  >= K2) Print it.

Time Complexity :   O(log n) + O(k) , where n = no of nodes and k = no of keys printed.

Code:

void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    printbstKey(root->right,k1,k2);
    return;
}

To avoid unwanted traversals we can compare current node's

data with K1 for left subtree and K2 for right subtree.

void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    if(root->data>=k1)
        printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    if(root->data<k2)
        printbstKey(root->right,k1,k2);
    return;
}  

Check if a given Binary Tree is SumTree

Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.

Following is an example of SumTree.

            26
          /   \
         10    3 
       /    \    \
      4     6     3 

Solution:

For each node check the following,

Right child  : non-leaf

Left child   : non-leaf

  root->data==2*root->left->data + 2*root->right->data.

Right child  : leaf

Left child   : leaf 

 root->data==root->left->data + root->right->data.

Right child  : leaf

Left child   : non-leaf

 root->data==2*root->left->data + root->right->data.

Right child  : non-leaf

Left child   : leaf

 root->data==root->left->data + 2*root->right->data.

Code:

int isSumTree_reentrant(Tnode *root) {
    if (root == NULL)
        return 0;
    if (isleaf(root) == 1)
        return 1;
    int nleft = 0, nright = 0;
    if (root->left != NULL) {
        nleft = root->left->data;
        if (isleaf(root->left) == 0)
            nleft = 2 * nleft;
    }
    if (root->right != NULL) {
        nright = root->right->data;
        if (isleaf(root->right) == 0)
            nright = 2 * nright;
    }
    if (root->data != nleft + nright)
        return 0;
    int a = 1, b = 1;
    if (root->left != NULL)
        a = isSumTree_reentrant(root->left);
    if (root->right != NULL)
        b = isSumTree_reentrant(root->right);
    return a & b;
}