Binary trees interview questions : part 2

******Check if two binary trees are identical *************

  boolean areIdentical(Node root1, Node root2)
    {
 
        /* base cases */
        if (root1 == null && root2 == null)
            return true;
 
        if (root1 == null || root2 == null)
            return false;
 
        /* Check if the data of both roots is same and data of left and right
           subtrees are also same */
        return (root1.data == root2.data
                && areIdentical(root1.left, root2.left)
                && areIdentical(root1.right, root2.right));
    }
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

******Check if a BST tree is subtree of another tree*******

/* This function returns true if S is a subtree of T, otherwise false */
    boolean isSubtree(Node T, Node S)
    {
        /* base cases */
        if (S == null)
            return true;
 
        if (T == null)
            return false;
 
        /* Check the tree with root as current node */
        if (areIdentical(T, S))
            return true;
 
        /* If the tree with root as current node doesn't match then
           try left and right subtrees one by one */
        return isSubtree(T.left, S)
                || isSubtree(T.right, S);
    }
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

******Check if a given Binary Tree is SumTree********

    /* A utility function to get the sum of values in tree with root
     as root */
    int sum(Node node)
    {
        if (node == null)
            return 0;
        return sum(node.left) + node.data + sum(node.right);
    }
 
    /* returns 1 if sum property holds for the given
       node and both of its children */
    int isSumTree(Node node)
    {
        int ls, rs;
 
        /* If node is NULL or it's a leaf node then
           return true */
        if ((node == null) || (node.left == null && node.right == null))
            return 1;
 
        /* Get sum of nodes in left and right subtrees */
        ls = sum(node.left);
        rs = sum(node.right);
 
        /* if the node and both of its children satisfy the
           property return 1 else 0*/
        if ((node.data == ls + rs) && (isSumTree(node.left) != 0)
                && (isSumTree(node.right)) != 0)
            return 1;
 
        return 0;
    }
 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
 ******Level Order Tree Traversal******

   /* Given a binary tree. Print its nodes in level order
     using array for implementing queue  */
    void printLevelOrder()
    {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty())
        {

            /* poll() removes the present head. */
            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");

            /*Enqueue left child */
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }

            /*Enqueue right child */
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }

Binary trees interview questions : part 1

*****Program to count leaf nodes in a binary tree*****

getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
    Leaf count of a tree = Leaf count of left subtree +
                                 Leaf count of right subtree

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

****Convert a Binary Tree into its Mirror Tree*****

1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

check:
For two trees ‘a’ and ‘b’ to be mirror images, the following three conditions must be true:

1. Their root node’s key must be same
2. Left subtree of root of ‘a’ and right subtree root of ‘b’ are mirror.
3. Right subtree of ‘a’ and left subtree of ‘b’ are mirror.

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Find the Maximum Depth or Height of a Tree******

 maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Construct Tree from given Inorder and Preorder traversals*****

Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

 Node buildTree(char in[], char pre[], int inStrt, int inEnd)
    {
        if (inStrt > inEnd)
            return null;

        /* Pick current node from Preorder traversal using preIndex
           and increment preIndex */
        Node tNode = new Node(pre[preIndex++]);

        /* If this node has no children then return */
        if (inStrt == inEnd)
            return tNode;

        /* Else find the index of this node in Inorder traversal */
        int inIndex = search(in, inStrt, inEnd, tNode.data);

        /* Using index in Inorder traversal, construct left and
           right subtress */
        tNode.left = buildTree(in, pre, inStrt, inIndex - 1);
        tNode.right = buildTree(in, pre, inIndex + 1, inEnd);

        return tNode;
    }

    int search(char arr[], int strt, int end, char value)
    {
        int i;
        for (i = strt; i <= end; i++)
        {
            if (arr[i] == value)
                return i;
        }
        return i;
    }

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
****Binary tree, print all root-to-leaf paths****

    void printPaths(Node node)
    {
        int path[] = new int[1000];
        printPathsRecur(node, path, 0);
    }

    /* Recursive helper function -- given a node, and an array
       containing the path from the root node up to but not
       including this node, print out all the root-leaf paths.*/
    void printPathsRecur(Node node, int path[], int pathLen)
    {
        if (node == null)
            return;

        /* append this node to the path array */
        path[pathLen] = node.data;
        pathLen++;

        /* it's a leaf, so print the path that led to here  */
        if (node.left == null && node.right == null)
            printArray(path, pathLen);
        else
        {
            /* otherwise try both subtrees */
            printPathsRecur(node.left, path, pathLen);
            printPathsRecur(node.right, path, pathLen);
        }
    }

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*****Print nodes at k distance from root******

    void printKDistant(Node node, int k)
    {
        if (node == null)
            return;
        if (k == 0)
        {
            System.out.print(node.data + " ");
            return;
        }
        else
        {
            printKDistant(node.left, k - 1);
            printKDistant(node.right, k - 1);
        }
    }
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*******Ancestors of a given node in Binary Tree*******

 boolean printAncestors(Node node, int target)
    {
         /* base cases */
        if (node == null)
            return false;

        if (node.data == target)
            return true;

        /* If target is present in either left or right subtree
           of this node, then print this node */
        if (printAncestors(node.left, target)
                || printAncestors(node.right, target))
        {
            System.out.print(node.data + " ");
            return true;

        /* Else return false */
        return false;
    }