Technical interviews: Tree

Question1:
Write a program to perform pre-order, in-order and post-order tree traversal.(Note: Non-recursive!)
See the solution 
 
package com.hong.tree;
import TreeNode;

import java.util.Stack;


/**
 * @author HongQing
 *
 */

public class NonRecursiveTraversal {
    
    //Tree pre-order traversal
    public static void preOrderTraversalNonRec(TreeNode root)
    {
        Stack<TreeNode> preOrderStack = new Stack<TreeNode>();
        TreeNode  currentNode; 
        
        preOrderStack.push(root);
        
        while(!preOrderStack.isEmpty())
        {
            currentNode = preOrderStack.pop(); 
            
            System.out.println(currentNode); //Prints out a node.
            if(currentNode.rightNode != null)
                preOrderStack.push(currentNode.rightNode);
            else 
                preOrderStack.push(currentNode.leftNode);
            
        }
        
    }
    
    //Tree in-order traversal.
    public static void inOrderTraversalNonRec(TreeNode root)
    {
        Stack<TreeNode> inorderStack = new Stack<TreeNode>(); 
        TreeNode current = root; 
        
        while(current != null)
        {
            inorderStack.push(current); 
            current = current.leftNode; 
        }
        while(!inorderStack.empty())
        {
            current = inorderStack.pop(); 
            System.out.printf("%d ",current.data);
            
            if(current.rightNode != null)
            {
                inorderStack.push(current.rightNode);
                TreeNode leftOfChild = current.rightNode.leftNode; 
                
                while( leftOfChild != null)
                {
                    inorderStack.push(leftOfChild);
                    leftOfChild = leftOfChild.leftNode;
                }   
            }
        }
    }
    
    //Tree post-order traversal
    public static void postOrderTraversalNonRec(TreeNode root)
    {
        Stack<TreeNode>  nodeStack  = new Stack<TreeNode>();
        Stack<TreeNode>  outputStack = new Stack<TreeNode>();
        
        nodeStack.push(root); 
        TreeNode current;
        while( !nodeStack.isEmpty() )
        {
            current  = nodeStack.pop();     
            outputStack.push(current); 
            
            if(current.leftNode != null)
                nodeStack.add(current.leftNode);
            if(current.rightNode != null)
                nodeStack.add(current.rightNode);
        }
        
        while(!outputStack.isEmpty())
        {
            current = outputStack.pop();    
            System.out.printf("%d ", current.data);
        }
    }
    

}
Question2: 
Write a program 
1. To compute the height of a tree. 
2. To test if a tree is balanced.
3. To verify that a tree is symmetric.
See the solution 
 
package com.hong.tree;

/**
 * @author HongQing
 *
 */
public class TreeHeightBalanceSymmetric {
    
    //Running time is O(N), since we just visit all nodes in the tree. 
    public static int getHeight(TreeNode root)
    {
        if(root == null)
            return 0; 
        return ( Math.max( getHeight(root.rightNode),  getHeight(root.leftNode)) + 1); 
    }
        
    //a balanced tree is defined to be a tree such that 
    //no two leaf nodes differ in distance from the root by more than one.
    public static  boolean isBalance(TreeNode root)
    {
        if(root == null)
            return true;
        
        //Check the difference between two children's height.
        if( getHeight(root.rightNode) - getHeight(root.leftNode) > 1 )
            return false; 
        
        return isBalance(root.rightNode) && isBalance(root.leftNode);
        
    }
    
    //Verifies a tree is symmetric.
    public boolean isSymmetric(TreeNode root)
    {
        if(root == null)
            return true; 
        else
            return isSymmetricHelper(root.leftNode, root.rightNode);
    }

    public boolean isSymmetricHelper(TreeNode leftNode, TreeNode rightNode)
    {
        //Base case checking.
       if(leftNode == null && rightNode == null)
           return true;
       if(leftNode == null && rightNode != null)
           return false;
       if(leftNode != null && rightNode == null)
           return false;
       
       //Checks recursively.
       return isSymmetricHelper(leftNode.leftNode, rightNode.rightNode) && isSymmetricHelper(leftNode.rightNode, rightNode.leftNode);
                  
    }
    
}
Question3:
You are given two binary trees. Write a program to check if the smaller one is subtree of the larger one.
See the solution 
package com.hong.tree;

/**
 * @author HongQing
 *
 */
public class Subtree {

    /**
     * @param big   Big tree.
     * @param small   Small tree.
     * @return true if big contains small, false otherwise.
     * 
     * Running time of this method is O(N*M) where N is the number of nodes in the big tree and M is the 
     * number of nodes in the small one.
     * 
     */
    public boolean  checkSubtree(TreeNode big, TreeNode small)
    {
        if(big == null) //The larger tree is empty, but the substree still not found.
            return false;
        
        if(matchTrees(big, small))
            return true;
        
        return checkSubtree(big.leftNode, small) || checkSubtree(big.rightNode, small);
    }
    
    //Checks if two trees are identical. 
    public boolean matchTrees(TreeNode tree1, TreeNode tree2 )
    {
        //Nothing left to compare, return true.
        if(tree1 == null && tree2 == null) 
            return true;
        
        if(tree1 == null || tree2 == null) 
            return false;
        
        if(tree1.data != tree2.data) 
            return false;
        
        return matchTrees(tree1.leftNode, tree2.leftNode) && matchTrees(tree1.rightNode, tree2.rightNode);
    }

}