finding lowest common ancestor in a binary tree

bt_lowest_common_ancestor.java

// Taken from CtCI-6th-Edition from @careercup


public class bt_lca {

    /* One node of a binary tree. The data element stored is a single 
     * character.
     */
    public class TreeNode {
    	public int data;      
    	public TreeNode left;    
    	public TreeNode right; 
    	public TreeNode parent;
    	private int size = 0;
    
    	public TreeNode(int d) {
    		data = d;
    		size = 1;
    	}
    	
    	private void setLeftChild(TreeNode left) {
    		this.left = left;
    		if (left != null) {
    			left.parent = this;
    		}
    	}
    	
    	private void setRightChild(TreeNode right) {
    		this.right = right;
    		if (right != null) {
    			right.parent = this;
    		}
    	}
    	
    	public void insertInOrder(int d) {
    		if (d <= data) {
    			if (left == null) {
    				setLeftChild(new TreeNode(d));
    			} else {
    				left.insertInOrder(d);
    			}
    		} else {
    			if (right == null) {
    				setRightChild(new TreeNode(d));
    			} else {
    				right.insertInOrder(d);
    			}
    		}
    		size++;
    	}
    	
    	public int size() {
    		return size;
    	}
    	
    	public boolean isBST() {
    		if (left != null) {
    			if (data < left.data || !left.isBST()) {
    				return false;
    			}
    		}
    		
    		if (right != null) {
    			if (data >= right.data || !right.isBST()) {
    				return false;
    			}
    		}		
    		
    		return true;
    	}
    	
    	public int height() {
    		int leftHeight = left != null ? left.height() : 0;
    		int rightHeight = right != null ? right.height() : 0;
    		return 1 + Math.max(leftHeight, rightHeight);
    	}
    	
    	public TreeNode find(int d) {
    		if (d == data) {
    			return this;
    		} else if (d <= data) {
    			return left != null ? left.find(d) : null;
    		} else if (d > data) {
    			return right != null ? right.find(d) : null;
    		}
    		return null;
    	}
    	
    	private static TreeNode createMinimalBST(int arr[], int start, int end){
    		if (end < start) {
    			return null;
    		}
    		int mid = (start + end) / 2;
    		TreeNode n = new TreeNode(arr[mid]);
    		n.setLeftChild(createMinimalBST(arr, start, mid - 1));
    		n.setRightChild(createMinimalBST(arr, mid + 1, end));
    		return n;
    	}
    	
    	public static TreeNode createMinimalBST(int array[]) {
    		return createMinimalBST(array, 0, array.length - 1);
    	}
    	
    	public void print() {
    		BTreePrinter.printNode(this);
    	}
    } 
	
	public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (!covers(root, p) || !covers(root, q)) { // Error check - one node is not in tree
			return null;
		}
		return ancestorHelper(root, p, q);
	}
	
	public static TreeNode ancestorHelper(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null || root == p || root == q) {
			return root;
		}
		
		boolean pIsOnLeft = covers(root.left, p);
		boolean qIsOnLeft = covers(root.left, q);
		if (pIsOnLeft != qIsOnLeft) { // Nodes are on different side
			return root;
		}
		TreeNode childSide = pIsOnLeft ? root.left : root.right;
		return ancestorHelper(childSide, p, q);
	}	
	
	public static boolean covers(TreeNode root, TreeNode p) { 
		if (root == null) return false;
		if (root == p) return true;
		return covers(root.left, p) || covers(root.right, p); 
	}
		
	
	
	public static void main(String[] args) {
		int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		TreeNode root = TreeNode.createMinimalBST(array);
		TreeNode n3 = root.find(1);
		TreeNode n7 = root.find(7);
		TreeNode ancestor = commonAncestor(root, n3, n7);
		System.out.println(ancestor.data);
	}

}