Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2 Output: 1
Constraints:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q will exist in the tree.Problem Overview: Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).
Approach 1: Path to Root Approach (O(n) time, O(n) space)
This approach records the path from the root to each target node. Run a DFS to build a list of nodes from the root to p, then repeat for q. Once both paths are available, iterate through them from the start and find the last common node before the paths diverge. That node is the lowest common ancestor. The tree traversal takes O(n) time in the worst case, and storing both paths requires O(n) extra space.
The method is easy to reason about because it converts the problem into comparing two arrays of ancestors. It works well when you want a clear conceptual model of ancestor relationships. The downside is the extra memory used to store both paths.
Approach 2: Recursive Depth-First Search (O(n) time, O(h) space)
This is the standard optimal solution. Traverse the tree using recursive DFS. If the current node is null, return null. If the current node matches p or q, return that node. Recursively search the left and right subtrees. If both recursive calls return non-null values, the current node is the first point where the two targets split across subtrees, making it the lowest common ancestor.
If only one side returns a node, propagate that result upward. Eventually the recursion bubbles the correct ancestor back to the root call. Each node is visited once, giving O(n) time complexity. The recursion stack consumes O(h) space where h is the tree height.
This approach works naturally with Tree recursion patterns and is commonly used in Depth-First Search problems. Since binary tree traversal is already required, the solution stays simple and avoids storing full paths.
Recommended for interviews: The recursive DFS solution is what interviewers typically expect. It demonstrates strong understanding of Binary Tree traversal and recursive reasoning. Mentioning the path-to-root approach first shows you understand the problem structure, but implementing the DFS solution proves you can optimize both memory usage and code simplicity.
This approach uses recursion to traverse the tree starting from the root. If the current node is either p or q, then the node is returned upwards in the recursion stack as the potential LCA. Otherwise, we continue to search both left and right subtrees. If both subtrees return non-null values, it means p and q are in different subtrees, and the current node is the LCA. If only one subtree returns a non-null value, it means both nodes are located in that subtree and that subtree's root should be the LCA.
This C code defines a recursive function to find the LCA of two nodes in a binary tree. It checks if the current node is NULL or matches either of the two nodes p or q and returns the node if true. It then recursively checks the left and right children. If both are non-null, the current node is the LCA; otherwise, it returns the non-null child.
Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node only once.
Space Complexity: O(N) due to the recursion stack when the tree is completely unbalanced.
The basic idea is to find the paths from the root to the two nodes p and q. Once you have the paths, compare them to find the deepest common node. This method is straightforward, using known operations to reconfirm ancestor status along determined paths.
In C, we maintain arrays to keep track of paths from the root to the target nodes and compare these paths to find their last common node.
Time Complexity: O(N) due to double traversal in finding paths for each node.
Space Complexity: O(H), where H is the height of the tree for storing path information.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | Time Complexity: |
| Path to Root Approach | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Path to Root Approach | O(n) | O(n) | Useful for understanding ancestor relationships or when explicit root-to-node paths are required. |
| Recursive Depth-First Search | O(n) | O(h) | Best general solution for binary trees. Minimal extra memory and standard interview approach. |
LOWEST COMMON ANCESTOR OF A BINARY TREE I | PYTHON | LEETCODE 236 • Cracking FAANG • 67,999 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode