236. Lowest Common Ancestor of a Binary Tree
Problem Description
In this problem, we are given the roots of a binary tree and two nodes from this tree. Our task is to find the lowest common ancestor (LCA) of these two nodes. The LCA of two nodes p
and q
is defined as the deepest node in the tree that has both p
and q
as descendants (with a node being allowed to be a descendant of itself).
Flowchart Walkthrough
To determine the appropriate algorithm for solving LeetCode problem 236, "Lowest Common Ancestor of a Binary Tree," we'll utilize the algorithm flowchart available at the Flowchart. Here's the step-by-step analysis using the flowchart:
Is it a graph?
- Yes: A binary tree is a specialized graph where nodes (elements of the tree) have at most two children, which makes them nodes in a graph.
Is it a tree?
- Yes: Specifically, the problem describes a binary tree, which is a type of tree.
Following the "yes" pathway from the question "Is it a tree?" leads us directly to apply DFS (Depth-First Search). This decision is based on the recognition that navigating or processing tree structures often involves Depth-First Search algorithms, which efficiently explore all the nodes by traversing as deep as possible into the tree before backtracking. This is particularly suitable for searching elements like ancestors where traversal from root to specific nodes or between nodes is necessary.
Conclusion: Given that the problem involves finding the lowest common ancestor in a binary tree, Depth-First Search is suitable for recursively exploring potential ancestries and thereby determining the lowest common ancestor. The flowchart confirms that DFS should be applied for tree-related problems where structures need to be explored deeply.
Intuition
The solution to this problem is based on a recursive traversal of the binary tree. When we traverse the tree, we are looking for three possible conditions at each node:
-
One condition is that we have found either node
p
orq
. In this case, the current node could potentially be the LCA. -
The second condition is that one of the nodes
p
orq
is found in the left subtree and the other is found in the right subtree of the current node. If this is the case, then the current node is the LCA forp
andq
, as it sits above both nodes in the tree. -
The third condition is that both nodes are located in either the left subtree or the right subtree of the current node. In this instance, the lowest common ancestor will be deeper in the tree, so we continue searching in the subtree that contains both nodes.
The base case for our recursion occurs when we reach a null
node (indicating that we've reached the end of a path and haven't found either p
or q
), or when we find one of the nodes p
or q
.
To implement this intuition, we use a recursive algorithm that will search for p
and q
starting from root
. At each step, we make a recursive call to search the left and right subtrees. If both recursive calls return non-null
nodes, it means we've found p
and q
in different subtrees of the current node, and thus the current node is the LCA. If only one of the subtrees contains one of the nodes (or both), we return that subtree's node, propagating it up the call stack. If neither subtree contains either of the nodes, we return null
.
This recursive approach continues until the LCA is found, or we've confirmed that p
and q
are not present in the binary tree.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
To implement the solution for finding the lowest common ancestor, the algorithm employs a depth-first search (DFS) pattern, which is a type of traversal that goes as deep as possible down one path before backing up and trying another. This pattern is particularly useful for working with tree data structures. Here is an overview of how the DFS is applied in this solution:
-
Recursive Function: The solution defines a recursive function
lowestCommonAncestor
which takes the current node (root
), and the two nodes we are finding the LCA for (p
andq
). Recursion leverages the call stack to perform a backtracking search, allowing us to explore all paths down the tree and retrace our steps. -
Base Case: The base case of the recursion occurs when either the current node is
null
, or the current node matches one of the nodes we're looking for (p
orq
). In this case, the function returns the current node, which may benull
or the matching node. -
Search Left and Right Subtrees: If the base case is not met, the algorithm recursively calls
lowestCommonAncestor
for the left and right children of the current node. These calls effectively search for the nodesp
andq
in both subtrees. -
Postorder Traversal: Since the recursion explores both left and right subtrees before dealing with the current node, this represents a postorder traversal pattern. After both subtrees have been searched, the algorithm processes the current node.
-
LCA Detection:
- If both the left and right subtree recursive calls return non-
null
nodes, it means bothp
andq
have been found in different subtrees, and therefore the current node is their lowest common ancestor. - If only one of the calls returns a non-
null
node, that indicates the current subtree contains at least one of the two nodes, and potentially both. The non-null
node is returned up the call stack. - If both calls return
null
, it means neitherp
norq
was found in the current subtree, andnull
is returned.
- If both the left and right subtree recursive calls return non-
-
Propagation of the LCA: The LCA, once found, is propagated up the call stack to the initial call, and ultimately returned as the result of the function.
Here is the implementation of the algorithm in the reference solution provided:
class Solution:
def lowestCommonAncestor(
self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
if root is None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
return root if left and right else (left or right)
In the provided code snippet, the if
condition handles the base case, while the calls to lowestCommonAncestor(root.left, p, q)
and lowestCommonAncestor(root.right, p, q)
implement the recursive search. The final return statement decides which node to return based on whether the left and/or right calls found the nodes p
and q
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following binary tree:
A / \ B C / \ D E
In this binary tree, let's say we want to find the lowest common ancestor (LCA) of the nodes D and E.
-
We start our recursive function
lowestCommonAncestor
at the root node A. -
Since the root is neither null, nor is it D or E, we proceed to make recursive calls to both the left and right subtrees of A.
-
The left recursive call goes to node B. Again, B isn't null, D, or E, so we continue.
-
Recursively, for node B, we go left to D and right to E. Node D matches one of our target nodes, so the left call returns D to the call on B. Similarly, on the right side, the node E matches the other target node, so the right call returns E to the call on B.
-
With both sides of B returning a non-null node (D on the left and E on the right), we determine that B must be the LCA because it's the node where both target nodes D and E subtrees split. The function returns node B up to the call on A.
-
Since the recursive call on the left of A returned B (non-null) and the call on the right of A (to C) will return null (since neither D nor E is in that subtree), the final decision at A is based on whether one or both sides are non-null.
-
Since the right call returns null, and the left call returns B (non-null), the function finally returns B, the LCA of D and E.
Following the recursive definition used in our solution, we can confirm that node B is the lowest common ancestor of nodes D and E in this binary tree.
Solution Implementation
1class TreeNode:
2 def __init__(self, value):
3 self.value = value
4 self.left = None
5 self.right = None
6
7
8class Solution:
9 def lowestCommonAncestor(self, root: TreeNode, node1: TreeNode, node2: TreeNode) -> TreeNode:
10 # If the root is None, or the root is one of the nodes we're looking for,
11 # we return the root as the LCA (Lowest Common Ancestor)
12 if root is None or root == node1 or root == node2:
13 return root
14
15 # Look for the LCA in the left subtree
16 left_lca = self.lowestCommonAncestor(root.left, node1, node2)
17
18 # Look for the LCA in the right subtree
19 right_lca = self.lowestCommonAncestor(root.right, node1, node2)
20
21 # If both left and right LCA are non-null, it means one node is in the left
22 # subtree and the other is in the right, so root is the LCA
23 if left_lca and right_lca:
24 return root
25
26 # Otherwise, if one of the LCAs is non-null, return that one
27 return left_lca if left_lca else right_lca
28
1// Definition for a binary tree node.
2class TreeNode {
3 int val; // The value of the node
4 TreeNode left; // Reference to the left child
5 TreeNode right; // Reference to the right child
6
7 // Constructor to initialize the node with a value
8 TreeNode(int x) {
9 val = x;
10 }
11}
12
13class Solution {
14 /**
15 * Finds the lowest common ancestor of two nodes in a binary tree.
16 * @param root The root node of the binary tree.
17 * @param p The first node to find the ancestor for.
18 * @param q The second node to find the ancestor for.
19 * @return The lowest common ancestor node or null if not found.
20 */
21 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
22 // If the root is null or root is either p or q, then root is the LCA
23 if (root == null || root == p || root == q) return root;
24
25 // Recurse on the left subtree to find the LCA of p and q
26 TreeNode left = lowestCommonAncestor(root.left, p, q);
27 // Recurse on the right subtree to find the LCA of p and q
28 TreeNode right = lowestCommonAncestor(root.right, p, q);
29
30 // If finding LCA in the left subtree returns null, the LCA is in the right subtree
31 if (left == null) return right;
32 // If finding LCA in the right subtree returns null, the LCA is in the left subtree
33 if (right == null) return left;
34
35 // If both left and right are non-null, we've found the LCA at the root
36 return root;
37 }
38}
39
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int value;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
8 * };
9 */
10
11class Solution {
12public:
13 /* Function to find the lowest common ancestor (LCA) of two given nodes in a binary tree.
14 *
15 * @param root The root node of the binary tree.
16 * @param firstNode The first node for which the LCA is to be found.
17 * @param secondNode The second node for which the LCA is to be found.
18 * @return The LCA of the two nodes.
19 */
20 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* firstNode, TreeNode* secondNode) {
21 // If root is nullptr or root is one of the nodes, then root itself is the LCA.
22 if (!root || root == firstNode || root == secondNode) return root;
23
24 // Recursively find the LCA in the left subtree.
25 TreeNode* leftLCA = lowestCommonAncestor(root->left, firstNode, secondNode);
26 // Recursively find the LCA in the right subtree.
27 TreeNode* rightLCA = lowestCommonAncestor(root->right, firstNode, secondNode);
28
29 // If both the left and right subtrees contain one of the nodes each, then the current root is the LCA.
30 if (leftLCA && rightLCA) return root;
31
32 // If only one subtree contains both the nodes, return that subtree's LCA.
33 return leftLCA ? leftLCA : rightLCA;
34 }
35};
36
1// Definition for a binary tree node.
2class TreeNode {
3 val: number
4 left: TreeNode | null
5 right: TreeNode | null
6
7 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 this.val = (val === undefined ? 0 : val);
9 this.left = (left === undefined ? null : left);
10 this.right = (right === undefined ? null : right);
11 }
12}
13
14/**
15 * Finds the lowest common ancestor (LCA) of two nodes in a binary tree.
16 * The LCA is defined as the lowest node in T that has both p and q as descendants
17 * (where we allow a node to be a descendant of itself).
18 *
19 * @param root - The root node of the binary tree.
20 * @param p - The first node to find the LCA for.
21 * @param q - The second node to find the LCA for.
22 * @return The LCA node or null if either p or q is not present in the tree.
23 */
24function lowestCommonAncestor(
25 root: TreeNode | null,
26 p: TreeNode | null,
27 q: TreeNode | null,
28): TreeNode | null {
29 /**
30 * Recursively searches the binary tree to find the LCA of nodes p and q.
31 *
32 * @param currentNode - The current node being inspected in the binary tree.
33 * @return The LCA TreeNode, if it exists or null if not.
34 */
35 function findLCA(currentNode: TreeNode | null): TreeNode | null {
36 // If the current node is null, or we have found either p or q, return the current node
37 if (currentNode === null || currentNode === p || currentNode === q) {
38 return currentNode;
39 }
40
41 // Recursively search in the left subtree for one of the nodes
42 const leftSubtree = findLCA(currentNode.left);
43 // Recursively search in the right subtree for the other node
44 const rightSubtree = findLCA(currentNode.right);
45
46 // If both the left and right subtree calls return non-null, it means we have found the nodes p and q in both subtrees,
47 // so the current node is the LCA.
48 if (leftSubtree !== null && rightSubtree !== null) {
49 return currentNode;
50 }
51
52 // If only one of the subtrees contains one of the nodes, return that subtree; if neither contains any, return null.
53 return leftSubtree !== null ? leftSubtree : rightSubtree;
54 }
55
56 // Start the LCA search from the root node
57 return findLCA(root);
58}
59
Time and Space Complexity
The time complexity of the given code for finding the lowest common ancestor (LCA) in a binary tree is O(N)
, where N
is the number of nodes in the tree. This complexity arises because, in the worst-case scenario, the code will have to visit each node once to determine the LCA.
The space complexity of the code is O(H)
, where H
is the height of the binary tree. This is due to the recursive calls on the stack while the algorithm traverses down to find p
and q
. In the worst case of a skewed tree, H
can be N
, thereby having a space complexity of O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Want a Structured Path to Master System Design Too? Donāt Miss This!