235. Lowest Common Ancestor of a Binary Search 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 the tree has unique numbers. And both p & q exists in the tree.
Time Complexity: O(n) -> In worst case all nodes of the tree will be visited.
Space Complexity: O(height of the tree) -> In worst case height can be n if the tree is skewed.
*/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

/**
Iterative Solution
This solution assumes that the tree has unique numbers. And both p & q exists in the tree.
Time Complexity: O(height of the BST) -> In worst case height can be all nodes if the tree is skewed.
Space Complexity: O(1)
*/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
}

/**
Find the paths to p & q and then check for lca
Time Complexity:
findPath takes O(Tree Height) * 2
Comparing ancestors is O(Tree Height) as the ancestors array size can be max Tree Height.
Thus, total Time Complexity = O(Tree Height) -> tree height in case of skewed tree will be equal to number of nodes in the tree.
Space Complexity: O(Tree Height)
*/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        List<TreeNode> ancestorsP = new ArrayList<>();
        List<TreeNode> ancestorsQ = new ArrayList<>();

        if (!findPath(ancestorsP, root, p)) {
            return null;
        }
        if (!findPath(ancestorsQ, root, q)) {
            return null;
        }
        TreeNode lca = null;
        for (int i = 0; i < ancestorsP.size() && i < ancestorsQ.size(); i++) {
            if (ancestorsP.get(i) != ancestorsQ.get(i)) {
                break;
            }
            lca = ancestorsP.get(i);
        }
        return lca;
    }

    public boolean findPath(List<TreeNode> ancestors, TreeNode root, TreeNode node) {
        if (root == null) {
            return false;
        }
        ancestors.add(root);
        if (root == node) {
            return true;
        }
        if (node.val < root.val) {
            return findPath(ancestors, root.left, node);
        } else {
            return findPath(ancestors, root.right, node);
        }
    }
}