_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post:Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes
Let’s try the top-down approach where we traverse the nodes from the top to the bottom. First, if the current node is one of the two nodes, it must be the LCA of the two nodes. If not, we count the number of nodes that matches either p or q in the left subtree (which we call totalMatches). If totalMatches equals 1, then we know the right subtree will contain the other node. Therefore, the current node must be the LCA. If totalMatches equals 2, we know that both nodes are contained in the left subtree, so we traverse to its left child. Similar with the case wheretotalMatches equals 0 where we traverse to its right child.What is the run time complexity of this top-down approach? First, just for fun, we assume that the tree contains What if the tree is not necessarily balanced? Then in the worst case the complexity could go up to O(
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up. Sounds complicated? Surprisingly the code appears to be much simpler than the top-down one.
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post:Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5. In my last post: Lowest Common Ancestor of a Binary Tree Part I, we have devised a recursive solution which finds the LCA in O(
The run time complexity of this approach is O(
dh). If you observe carefully from the previous solution, the node which is closer to the root is alwaysdh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?The reason is simple, if we advance the deeper node
A variation of this problem which seemed to be more popular is:
I am sure you know how to answer this question now |

Algorithms > Trees >