First the given nodes
q are to be searched in a binary tree and then their lowest common ancestor is to be found. We can resort to a normal tree traversal to search for the two nodes. Once we reach the desired nodes
q, we can backtrack and find the lowest common ancestor.
Approach 1: Recursive Approach
The approach is pretty intuitive. Traverse the tree in a depth first manner. The moment you encounter either of the nodes
q, return some boolean flag. The flag helps to determine if we found the required nodes in any of the paths. The least common ancestor would then be the node for which both the subtree recursions return a
True flag. It can also be the node which itself is one of
q and for which one of the subtree recursions returns a
Let us look at the formal algorithm based on this idea.
- Start traversing the tree from the root node.
- If the current node itself is one of
q, we would mark a variable
Trueand continue the search for the other node in the left and right branches.
- If either of the left or the right branch returns
True, this means one of the two nodes was found below.
- If at any point in the traversal, any two of the three flags
True, this means we have found the lowest common ancestor for the nodes
Let us look at a sample tree and we search for the lowest common ancestor of two nodes
11 in the tree.
Following is the sequence of nodes that are followed in the recursion:
1 --> 2 --> 4 --> 8 BACKTRACK 8 --> 4 4 --> 9 (ONE NODE FOUND, return True) BACKTRACK 9 --> 4 --> 2 2 --> 5 --> 10 BACKTRACK 10 --> 5 5 --> 11 (ANOTHER NODE FOUND, return True) BACKTRACK 11 --> 5 --> 2 2 is the node where we have left = True and right = True and hence it is the lowest common ancestor.
Time Complexity: , where is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
Space Complexity: . This is because the maximum amount of space utilized by the recursion stack would be since the height of a skewed binary tree could be .
Approach 2: Iterative using parent pointers
If we have parent pointers for each node we can traverse back from
q to get their ancestors. The first common node we get during this traversal would be the LCA node. We can save the parent pointers in a dictionary as we traverse the tree.
- Start from the root node and traverse the tree.
- Until we find
qboth, keep storing the parent pointers in a dictionary.
- Once we have found both
q, we get all the ancestors for
pusing the parent dictionary and add to a set called
- Similarly, we traverse through ancestors for node
q. If the ancestor is present in the ancestors set for
p, this means this is the first ancestor common between
q(while traversing upwards) and hence this is the LCA node.
Time Complexity : , where is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
Space Complexity : . In the worst case space utilized by the stack, the parent pointer dictionary and the ancestor set, would be each, since the height of a skewed binary tree could be .
Approach 3: Iterative without parent pointers
In the previous approach, we come across the LCA during the backtracking process. We can get rid of the backtracking process itself. In this approach we always have a pointer to the probable LCA and the moment we find both the nodes we return the pointer as the answer.
- Start with root node.
- Put the
(root, root_state)on to the stack.
root_statedefines whether one of the children or both children of
rootare left for traversal.
- While the stack is not empty, peek into the top element of the stack represented as
- Before traversing any of the child nodes of
parent_nodewe check if the
parent_nodeitself is one of
- First time we find either of
q, set a boolean flag called
True. Also start keeping track of the lowest common ancestors by keeping a note of the top index of the stack in the variable
LCA_index. Since all the current elements of the stack are ancestors of the node we just found.
- The second time
parent_node == p or parent_node == qit means we have found both the nodes and we can return the
- Whenever we visit a child of a
parent_nodewe push the
(parent_node, updated_parent_state)onto the stack. We update the state of the parent since a child/branch has been visited/processed and accordingly the state changes.
- A node finally gets popped off from the stack when the state becomes
BOTH_DONEimplying both left and right subtrees have been pushed onto the stack and processed. If
Truethen we need to check if the top node being popped could be one of the ancestors of the found node. In that case we need to reduce
LCA_indexby one. Since one of the ancestors was popped off.
LCA_indexwould be pointing to an index in the stack which would contain all the common ancestors between
q. And the
LCA_indexelement has the
lowestancestor common between p and q.
The animation above shows how a stack is used to traverse the binary tree and keep track of the common ancestors between nodes
Time Complexity : , where is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree. The advantage of this approach is that we can prune backtracking. We simply return once both the nodes are found.
Space Complexity : . In the worst case the space utilized by stack would be since the height of a skewed binary tree could be .