Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)

Описание: Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Given the root of a binary tree and 2 references of nodes that are in the binary tree, find the lowest common ancestor of the 2 nodes. The nodes do not have parent pointers.

The Approach

So there are many modulations of this problem where you can build a hashtable and make parent pointers, etc. We will focus on the recursive solution.


The Algorithm

The key is that we want to root ourselves at a node and then search left and then right for either of the 2 nodes given.

If we see either node, we will return it, if we do not find the node in a subtree search the value of null will be returned and bubbled up.

After we search both left and right we ask ourselves what our results mean.

If we found nothing to the left, we just bubble up what is on the right (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.

If we found nothing to the right, we just bubble up what is on the left (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.

If both the right and left result are not null, we have found our LCA.


Why?

We know it is an ancestor at the least but we definitely know it is the lowest common ancestor because we went bottom upwards, whatever we hit will be the LCA and it will bubble up.


Complexities

Time: O( n )

We will be touching the whole tree in the search, there are n nodes in the tree and we do O(1) work at each node. There are not exactly n calls though but I need to double check this...I need to solve the recurrence but oh well...we know it will stay linear in the asymptotic regard.

Space: O( h )

Stack usage at maximum will be the trees height. Worst case would be O(n) if our tree is skewed purely to the left or right and we need to find deep nodes. But n IS h in that case. But we say O( n ) in that case since it is more accurate to what is happening, the tree's size in nodes dominating the height.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson:    / vsympathyv  

Success In Tech:    / @successintech