Solution 1: Recursive - Faster
- Time Complexity: O(n)
- Space Complexity: O(h) - for recursive call stack
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; // If(left != null && right != null)
}
}
Solution 2: Iterative - Using parent pointers - Slower
- Time Complexity: O(n) - In the worst case we might be visiting all the nodes of binary tree.
- Space Complexity: O(n) - Space utilized the parent pointer Hash-table, ancestor_set and queue, would be O(n) each.
class Solution
{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
HashSet<TreeNode> ancestors_set = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
parent_map.put(root, null);
queue.add(root);
while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
{
TreeNode node = queue.poll();
if(node.left != null)
{
parent_map.put(node.left, node);
queue.add(node.left);
}
if(node.right != null)
{
parent_map.put(node.right, node);
queue.add(node.right);
}
}
while(p != null)
{
ancestors_set.add(p);
p = parent_map.get(p);
}
while(!ancestors_set.contains(q))
q = parent_map.get(q);
return q;
}
}