236. Lowest Common Ancestor of a Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
Recursive Solution.
This solution assumes that both nodes are present in the tree.
Time Complexity : O(n) - Worst case all nodes will be visisted once.
Space Complexity: O(n) - In worst case of skewed tree, the recursion stack can grow upto n.
*/
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 == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

/**
Recursive Solution
This solution handles the input nodes if they are not present in the given tree. It will return null if it is not able to find either or both nodes in the tree.
Time Complexity: O(n) - Worst case all nodes will be visited constant number of times.
Space Complexity: O(n) - In worst case of skewed tree, the recursion stack can grow upto n.
*/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        boolean[] present = new boolean[2];
        TreeNode lca = lowestCommonAncestorHelper(present, root, p, q);
        if (present[0] && present[1]) {
            return lca;
        }
        return null;
    }

    public TreeNode lowestCommonAncestorHelper(boolean[] present, TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return null;
        }
        TreeNode temp = null;
        if (node == p) {
            present[0] = true;
            temp = node;
        }
        if (node == q) {
            present[1] = true;
            temp = node;
        }
        TreeNode left = lowestCommonAncestorHelper(present, node.left, p, q);
        TreeNode right = lowestCommonAncestorHelper(present, node.right, p, q);
        if (temp != null) {
            return temp;
        }
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return node;
        }
    }
}

/**
Iterative Solution.
BFS to find all node <-> parent relations. Then find the ancestors of P and then check if Q's ancestor part of P's ancestors.
This solution assumes that both nodes are present in the tree.
Time Complexity : O(n) - All nodes will be visisted constant number of times..
Space Complexity: O(n) - all nodes will be saved in the HashMap
*/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        HashSet<TreeNode> ancestorsOfP = new HashSet<>();
        TreeNode P = p;
        TreeNode Q = q;
        queue.offer(root);
        map.put(root, null);
        while (!queue.isEmpty() && (!map.containsKey(p) || !map.containsKey(q))) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                map.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                map.put(node.right, node);
                queue.offer(node.right);
            }
        }
        while (P != null) {
            ancestorsOfP.add(P);
            P = map.get(P);
        }
        while (!ancestorsOfP.contains(Q)) {
            Q = map.get(Q);
        }
        return Q;
    }
}

// Also refer to https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/65245/Iterative-Solutions-in-PythonC++