Lowest Common Ancestor of a Binary Tree

				
					class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null || root==p || root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if ((left==p && right==q) || (left==q && right==p)) return root;
        if (left!=null) return left;
        return right;
    }
}
				
			

Since for every node in a binary tree it is guaranteed that we have a single unique path, we can check “post order” if we found both nodes that we search in the right and left sub trees. in any case we found such node, it is the LCA.