Binary Tree Implementation (Java Code)

Node.java
/**
 *
 * @author santosh
 */

public class Node {
   
     Node left;
     Node right;
     Node parent;
     int     val;
     int     height;
     int     balanceFactor;
     int     NaV = -99999999; // not a value.
   
    public Node(){
        left = right = parent = null;
        val = height = balanceFactor = NaV;
    }
   
    public Node(int val){
        left = right = parent = null;
        this.val = val;
        height = balanceFactor = NaV;
    }
   
    public Node(int val, int key){
        left = right = parent = null;
        this.val = val;
        this.balanceFactor = key;
        height = NaV;
    }
}

BST.java

/**
 *
 * @author santosh
 */
public class BST {

    private Node root;
   
    public BST(){
        root = null;
    }
   
    /**
     * Insert a node in given tree.
     * @param val
     */
    public void insert(int val){
       
        Node t = new Node(val);
        if(root == null){
            root = t;
            return;
        }else{
            Node temp = root, prev = null;
            while(temp != null){
                prev = temp;
                if(val > temp.val){
                    temp = temp.right;
                }else{
                    temp = temp.left;
                }
            }
           
            t.parent = prev; // assign the parent to new node;
           
            if(val > prev.val)
                prev.right = t;
            else
                prev.left = t;
        }
        return;
    }
   
    /**
     * Find the node whose data is given.
     * @param t
     * @param val
     * @return
     */
    public Node findNode(Node t, int val){
       
        Node temp = null;
       
        if(t != null && t.val == val)
            return t;
       
        if(t.left != null)
            temp = findNode(t.left, val);
        if(temp == null & t.right != null)
            temp = findNode(t.right, val);
       
        return temp;
    }
   
    /**
     * Returns the min value in a non-empty binary search tree.
     * @param t
     * @return
     */
    public Node findMin(Node t){
       
        if(t != null && t.left == null)
            return t;
        else
            return findMin(t.left);
    }
   
    /**
     * Returns the min value in a non-empty binary search tree.
     * @param t
     * @return
     */
    public Node findMax(Node t){
       
        if(t != null && t.right == null)
            return t;
        else
            return findMax(t.right);
    }
   
    /**
     * Print path of each leaf node in recursive order.
     * @param sum
     * @param t
     * @return
     */
    public int printPath(int sum, Node t){
       
        while(t != null){
            System.out.print("\t" + t.val);
            sum += t.val;
            t = t.parent;
        }
        return sum;
    }
   
    /**
     * Print leaf nodes
     * @param t
     */
    public void printLeafNodes(Node t){
       
        if(t != null && t.left == null && t.right == null){
            System.out.print("\t" + t.val);
        }
       
        if(t != null){
            printLeafNodes(t.left);
            printLeafNodes(t.right);
        }
       
        return;
    }
   
    /**
     * find path for each leaf node
     * @param t
     */
    public void findPath(Node t){
        if(t != null && t.left == null && t.right == null) {
            System.out.print("Path: ");
            int sum = printPath(0, t);
            System.out.println("\tSum: " + sum);
        }
        if(t != null){
            findPath(t.left);
            findPath(t.right);
        }
        return;
    }
   
    /**
     * Check if any path has given sum.
     * @param t
     * @param sum
     * @return
     */
    public boolean hasPathSum(Node t, int sum){
        if(t == null)
            return (sum == 0);
        else{
            sum -= t.val;
            return hasPathSum(t.left, sum) || hasPathSum(t.right, sum);
        }
    }
   
    /**
     * Make mirror image of given tree.
     * @param t
     */
    public void mirrorTree(Node t){
       
        if(t == null)
            return;
       
        Node temp = null;
        mirrorTree(t.left);
        mirrorTree(t.right);
       
        temp = t.left;
        t.left = t.right;
        t.right = temp;
       
        return;
    }
   
    /**
     * For each node in a binary search tree, create a new duplicate node, and insert
     * the duplicate as the left child of the original node.
     * The resulting tree should still be a binary search tree. So the tree...
     *          2
     *         / \
     *        1   3
     * Is changed to...
     *          2
     *         / \
     *        2   3
     *      /    /
     *     1    3
     *    /
     *   1
     *
     **/
    public void doubleTree(Node t){
       
        if(t == null)
            return;
       
        Node oldLeft = null;
        doubleTree(t.left);
        doubleTree(t.right);
       
        oldLeft = t.left;
        t.left = new Node(t.val);
        t.left.parent = t; // assign parent to new node
        t.left.left = oldLeft;
        if(t.left.left != null)
            t.left.left.parent = t.left; // update the parent for old node
       
    }
   
    /**
     * Given two trees, return true if they are structurally identical.
     * @param t1
     * @param t2
     * @return
     */
    public boolean checkMatchingTree(Node t1, Node t2){
     
        // both empty
        if(t1 == null && t2 == null)
            return true;
       
        else if(t1 != null && t2 != null)
            return (t1.val == t2.val &&
                    checkMatchingTree(t1.left, t2.left) &&
                    checkMatchingTree(t1.right, t2.right));
        else // one of them empty
            return false;
    }
   
    /**
     * Count number of nodes in a given tree.
     * @param t
     * @return
     */
    public int countTNode(Node t){
       
        if(t == null)
            return 0;
        else
            return (countTNode(t.left) + 1 + countTNode(t.right));
           
    }
   
    /**
     * For the key values 1...numKeys, how many structurally unique binary
     * search trees are possible that store those keys?
     * Strategy: consider that each value could be the root.
     * Recursively find the size of the left and right subtrees.
     * @param key
     * @return
     */
    public int countTrees(int key){
       
        if(key <= 1)
            return 1;
        else{
            // there will be one value at the root, with whatever remains
            // on the left and right each forming their own subtrees.
            // Iterate through all the values that could be the root...
            int sum = 0;
            int lht, rht, rt = 0;
           
            for(rt=1; rt<=key; rt++ ){
                lht = countTrees(rt-1);
                rht = countTrees(key-rt);
               
                // number of possible trees with this root == left*right
                sum += lht * rht;
            }
           
            return sum;
        }
    }
   
    /**
     * Find the maximum depth of a given tree.
     * @param t
     * @return
     */
    public int maxDept(Node t){
       
        if(t == null)
            return 0;
       
        int lDepth = maxDept(t.left);
        int rDepth = maxDept(t.right);
       
        return (lDepth>rDepth)?(lDepth+1):(rDepth+1);
       
    }
   
    /**
     * Print the tree in In-Order.
     * @param t
     */
    public void printInOrder(Node t){
        if(t == null)
            return;
       
        printInOrder(t.left);
        System.out.print("\t"+t.val);
        printInOrder(t.right);
    }
   
    /**
     * print the tree in Post-Order.
     * @param t
     */
    public void printPostOrder(Node t){
        if(t == null)
            return;
       
        printPostOrder(t.left);
        printPostOrder(t.right);
        System.out.print("\t"+t.val);
       
    }
   
    /**
     * Print the tree in Pre-order.
     * @param t
     */
    public void printPreOrder(Node t){
        if(t == null)
            return;
       
        System.out.print("\t"+t.val);
        printPreOrder(t.left);
        printPreOrder(t.right);
    }
   
    /**
     * Get root of the node.
     * @return
     */
    public Node getRoot(){
        return root;
    }
}