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.To solve #236 Lowest Common Ancestor of a Binary Tree, the key idea is to explore the tree using Depth-First Search (DFS). The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both nodes as descendants. In a binary tree (not necessarily a BST), we cannot rely on ordering properties, so we must traverse the tree.
A common strategy is a recursive DFS. Starting from the root, we search the left and right subtrees for the target nodes. If the current node matches either p or q, we return it as a potential ancestor. When both the left and right recursive calls return non-null values, it means one node was found in each subtree, making the current node the LCA.
This approach efficiently finds the ancestor in a single traversal of the tree. Because every node may be visited once, the time complexity is O(n), where n is the number of nodes. The recursive stack contributes O(h) space complexity, where h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS Recursive Traversal | O(n) | O(h) |
take U forward
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.
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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right =
The JavaScript code implements a straightforward recursion strategy similar to other languages. It recursively checks the presence of p or q and uses the results from left and right recursive calls to determine the potential LCA.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this is a very common interview question at FAANG and other top tech companies. It tests understanding of tree traversal, recursion, and problem decomposition using DFS.
A binary tree structure combined with recursion (or a stack for iterative DFS) is typically used. The algorithm relies on tree traversal rather than auxiliary data structures, making recursion the most common and intuitive method.
The optimal approach uses a recursive depth-first search. During traversal, each node checks whether the targets appear in its left or right subtree. If both sides return a match, the current node is the lowest common ancestor.
In a binary search tree, the LCA can be found using value comparisons because nodes follow an ordered property. In a general binary tree, no such ordering exists, so we must search both subtrees using DFS to locate the common ancestor.
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.