How do you solve Lowest Common Ancestor of a Binary Tree on LeetCode?

Lowest Common Ancestor of a Binary Tree (LeetCode #236) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: The LCA can be found using a single traversal of the tree.

What is the time complexity of Lowest Common Ancestor of a Binary Tree?

The optimal solution for Lowest Common Ancestor of a Binary Tree runs in O(n) time and uses O(h) space. The time complexity is O(n) because we visit each node once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

What is the brute force solution for Lowest Common Ancestor of a Binary Tree?

The brute force approach for Lowest Common Ancestor of a Binary Tree is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves finding the path from the root to each of the nodes p and q, and then comparing these paths to find the last common node. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Lowest Common Ancestor of a Binary Tree?

Lowest Common Ancestor of a Binary Tree uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Lowest Common Ancestor of a Binary Tree?

Explain your thought process clearly as you code. Consider edge cases, like when one of the nodes is the root. Practice tree traversal techniques before the interview.

What are common mistakes when solving Lowest Common Ancestor of a Binary Tree?

Students often forget to check if the current node is null. Confusing the return values when both left and right are non-null.

#236

Lowest Common Ancestor of a Binary Tree

Medium

TreeDepth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a recursive depth-first search (DFS) to find the LCA directly without storing paths. This is efficient because it only traverses the tree once.

⚙️

Algorithm

5 steps

1Step 1: If the current node is null, return null.
2Step 2: If the current node is either p or q, return the current node.
3Step 3: Recursively search the left and right subtrees.
4Step 4: If both left and right calls return non-null, the current node is the LCA.
5Step 5: If only one side returns a non-null node, return that node.

solution.py16 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
10        if not root or root == p or root == q:
11            return root
12        left = self.lowestCommonAncestor(root.left, p, q)
13        right = self.lowestCommonAncestor(root.right, p, q)
14        if left and right:
15            return root
16        return left if left else right

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1The LCA can be found using a single traversal of the tree.
2Understanding recursion is crucial for tree problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.