Check two trees are identical or not

Problem:

Given two binary trees, write a function to check if they are equal or not.

Solution:

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Algorithm:

isTreesIdenticalRec(Node root1, Node root2) :

1. Termination Condition: If both trees are empty then return true.

2. else if both trees are non-empty

     (a) Check data of the root nodes (root1->data ==  root2->data)

     (b) Check left subtrees recursively

                   call isTreesIdenticalRec(root1->left, root2->left)

     (c) Check right subtrees recursively

                   call isTreesIdenticalRec(root1->right, root2->right)

     (d) If a,b and c are true then return true.

3. else return false(=one is empty and another is not).

package crack.coding.interview;

/**

 * Class to check whether two binary trees are identical.

 * @author rajesh.dixit

 */

classIdenBinaryTree {

    

     /**

      * @author rajesh.dixit

      * Node of the Tree.

      */

     private static classNode {

           int data;

           Node left, right;

           Node(int item) {

                data = item;

                left = right = null;

           }

     }

    

     Node root1, root2;

    

     /**

      * To check whether Trees are Identical or not.

      * @param root1

      * @param root2

      * @return true/false

      */

     private static boolean isTreesIdenticalRec(Node root1, Node root2) {

          

           if(root1==null&& root2==null) {

                return true;

           } else if(root1!=null&& root2!=null) {

                return(root1.data == root2.data

                           && isTreesIdenticalRec(root1.left, root2.left)

                           && isTreesIdenticalRec(root1.right, root2.right));

           } else {

                return false;

           }

     }

     /**

      * Main method: Program start point.

      * @param args

      */

     public static void main(String[] args) {

          

           IdenBinaryTree tree1 = new IdenBinaryTree();

           tree1.root1 = new Node(1);

           tree1.root1.left = new Node(2);

           tree1.root1.right = new Node(3);

           tree1.root1.left.left = new Node(4);

           tree1.root1.left.right = new Node(5);

           IdenBinaryTree tree2 = new IdenBinaryTree();

           tree2.root2 = new Node(1);

           tree2.root2.left = new Node(2);

           tree2.root2.right = new Node(3);

           tree2.root2.left.left = new Node(4);

           tree2.root2.left.right = new Node(5);

           if (isTreesIdenticalRec(tree1.root1, tree2.root2)) {

                System.out.println("Trees are identical");

           } else {

                System.out.println("Trees are not identical");

           }

     }

}

Find the Maximum Depth or Height of a Tree

Call the depth function recursively

1. if Sub tree/tree is empty then return 0

2. else get maximum depth in left sub tree and right sub tree + 1.

class Tree {

   int value;

   Tree left;

   Tree right;

   public Tree (int value) {

      this.value = value;

   }

}

public classFindMaxDepth {

   private static int depth(Tree tree) {

      if(tree==null) {

         return 0;

      } else {

         return Math.max(depth(tree.left), depth(tree.right)) + 1;

      }

   }

   public static voidmain(String[] args) {

      Tree root = new Tree(1);

      root.left = new Tree(2);

      root.right = new Tree(3);

      root.left.left = new Tree(7);

      root.left.right = new Tree(6);

      root.right.left = new Tree(5);

      root.right.right = new Tree(4);

      root.left.left.left = new Tree(8);

      root.left.left.right = new Tree(9);

      root.left.left.left.left = new Tree(11);

      root.left.left.left.right = new Tree(10);

      System.out.println(depth(root));

   }

}

Level order traversal in spiral form

1. Use two stacks.

      One stack for print the elements from left to right,

      Other stack to print the elements from right to left.

2. In every iteration, we have nodes of one level,

   We will print the nodes and keep pushing the child nodes in another stack.

import java.util.Stack;

class Tree {

   int value;

   Tree left;

   Tree right;

   public Tree (int value) {

      this.value = value;

   }

}

public class PrintSpriralTree {

   public static void main(String[] args) {

      Tree root = new Tree(1);

      root.left = new Tree(2);

      root.right = new Tree(3);

      root.left.left = new Tree(7);

      root.left.right = new Tree(6);

      root.right.left = new Tree(5);

      root.right.right = new Tree(4);

      root.left.left.left = new Tree(8);

      root.left.left.right = new Tree(9);

      root.left.left.left.left = new Tree(11);

      root.left.left.left.right = new Tree(10);

      printSpiral(root);

   }

   private static void printSpiral(Tree root) {

      Stack<Tree> s1 = new Stack<Tree>();

      Stack<Tree> s2 = new Stack<Tree>();

      s1.add(root);

      while(!s1.isEmpty() || !s2.isEmpty()) {

        

         while(!s1.isEmpty()) {

            Tree top = s1.pop();

            System.out.print(top.value+" ");

           

            if(top.right!=null) {

               s2.add(top.right);

            }

           

            if(top.left!=null) {

               s2.add(top.left);

            }

         }

        

         while(!s2.isEmpty()) {

            Tree top = s2.pop();

            System.out.print(top.value + " ");

           

            if(top.left!=null) {

               s1.add(top.left);

            }

           

            if(top.right!=null) {

               s1.add(top.right);

            }           

         }

      }

   }

}

Spiral order traversal will take O(n) time and O(n) extra space.