This is a series of problems related to find the lowest common ancestor of binary tree. If the tree node has a pointer to its parent, then it is relatively easy to find the lowest common ancestor. But a tree has only left and right pointers to its subtree.

• Leetcode - 235
• Leetcode - 236

Leetcode 235 and 236 has only one difference where 235 is for binary search tree, which could make it a little bit easier. But both problem could be solved by treat the tree as a general tree, and the time complexity are both O(n).

Naturally, we could thought it as a post order trasverse problem, because we want to find the common parent of both p and q. Consider what we should do, if we have the results from the left subtree and right subtree, a few cases:

1. If p is in left/right, and q is in right/left, then current node is a common parent; If we return it at the lowest level, then it is the lowest common ancestor.
2. If current node is p/q, and q/p is in right or left, then current node is the lowest common ancestor, we can return it.
3. If none of p/q is in left and right, then return null.
4. If p or q is in only one subtree, either p or q, then we should return it to upper level.
5. If current node is p or q, then we can return the current node.

Since p and q will exist in the tree is one of the constraints, we could swim up the lowest common ancestor to the root, as in the worst case, root is the lowest common ancestor anyway.

In fact, the cases 2, 5 could be consolidated to: If current node is p or q, return it. Because p and q must exist in the tree, if we see p, we might either see q at the current subtree, which means p is the lowest common ancestoer. Or we could see q at upper level, then case 1 could be captured.

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

What if the existance constraint is not valid? This is below:

• Leetcode - 1644

We could centainly trasverse the tree and check if p and q exist in the tree, and then use the above approach. This requires two passes.

Another approach is using one pass, where when Cases 1 or 2 are valid, then we set the lowest common ancestor. If we only get p or q, we only return it to upper level for handling.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     
        lca(root, p, q);
        return lca;
    }
    private TreeNode lca;
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        
        //case 1
        if ((left == p && right == q) || (left == q && right == p)) {
            lca = root; 
            return null;
        }
        //case 2
        if ( (root == p || root == q) && (left != null || right != null)) {
            lca = root;
            return null;
        }
        //otherwise
        if (root == p || root == q) return root;
        return left != null ? left : right;
    }

In above problems, we only cares about two nodes, what if there are more than two nodes? This is Leetcode - 1676

• Leetcode - 1676

With the condition of existance, we could use the same algorithm before, with adding some further check on the node.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        //use set to speed up checking
        Set<TreeNode> allnodes = new HashSet<>();
        for (TreeNode node : nodes) {
            allnodes.add(node);
        }
        return lca(root, allnodes);
    }
    
    private TreeNode lca(TreeNode p, Set<TreeNode> nodes) {
        if (p == null) return p;
        
        if (nodes.contains(p)) return p;

        TreeNode left = lca(p.left, nodes);
        TreeNode right = lca(p.right, nodes); 
        
        if (left != null && right != null) return p;
        
        return left != null ? left : right;

    }

As stated before, if tree node has a parent pointer, the problem is much simpler as in Leetcode 1650.

• Leetcode - 1650

Just use one set to record one path from p to root, and exame the other path.

    public Node lowestCommonAncestor(Node p, Node q) {        
        
        Set<Node> set = new HashSet<>();
        
        while (p != null) {
            set.add(p);
            p = p.parent;
        }
        
        while(q != null) {
            
            if (set.contains(q)) return q;
            q = q.parent;
            
        }
        return null;
    }