AlgoDaily - Lowest Common Ancestor

Good morning! Here's our prompt for today.

In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken:

Identify every component that renders something based on that state.
Find a common owner component (a single component above all the components that need the state in the hierarchy).
Either the common owner or another component higher up in the hierarchy should own the state.

This is an algorithmic problem-- let's find the lowest common ancestor!

You're given a binary search tree tree1 and two of its child nodes as parameters. Can you write a method lowestCommonAncestor(root: Node, node1: Node, node2: Node) to identify the lowest common ancestor of the two nodes? The lowest common ancestor is the deepest node that has both of the two nodes as descendants.

In the below example, the lowest common ancestor of node 5 and 8 is 7.

SNIPPET

1/*
2       7
3      / \
4     4   8
5    / \
6   1   5
7*/

The method will called in the following manner: lowestCommonAncestor(root, node1, node2);.

You can assume our standard node definition for the tree vertices:

1# Node definition
2class Node:
3    def __init__(self, val):
4        self.val = val
5        self.left = None
6        self.right = None

Bonus: is there a way to find the lowest common ancestor of two nodes if the root wasn't passed as a parameter?

Constraints

Number of nodes in the BST <= 1000
The nodes will always contain integer values between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx
​
 
def least_common_ancestor(root, node_1, node_2):
    # fill
    return root
​
​
# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
​
​
# Regular binary trees
tree1 = Node(4)
tree1.left = Node(1)
tree1.right = Node(3)
​
tree2 = Node(5)
tree2.left = Node(10)
tree2.left.left = Node(17)
tree2.left.right = Node(3)
tree2.right = Node(8)
​
# Binary search trees
tree3 = Node(6)
tree3.left = Node(3)
​
tree4 = Node(5)

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?

The problem could be initially intimidating if you've never heard of the term lowest common ancestor. However, once you realize that it's just the highest shared parent that two nodes have in common, it's easy to visualize ways to use some form of traversal to our advantage.

One way to go about this problem is to visualize the traversal path required from the leaves. We'd probably want to move towards the top since that's where the ancestor is. In other words, we would follow the nodes upwards to get to the lowest common ancestor. This means if we wanted to find the LCA of 2 and 9 below, we'd first trace 2 upwards (so the path followed goes 2 -> 4 -> 6).

xxxxxxxxxx
 
/*
       6 
      / \ 
     4   9 
    / \
   2   5
  / \
 1   3
*/

Then, we'd repeat this for 9 (9 -> 6).

See something in common? The final nodes of both paths ended up being the same (node 6). We are thus able to conclude that 6 is the lowest common ancestor, as it's by definition the highest node they have in common (note that there can more than one shared ancestor, but this is the lowest in the branching chain).

If we think about possible solutions, what do we need to do? The solution we want is a traversal to find the first difference in node-to-root path. Is there anything about BST properties that could help us traverse upwards while starting from the root?

Let's revisit some Binary Search Tree properties and start with a basic question about binary trees:

Try this exercise. Click the correct answer from the options.

What is the name of the top-most node in a binary tree?

Click the option that best answers the question.

The peak
The root
The flesh
The apple

Look at this BST, and let's say we're looking for 4 and 8's LCA:

xxxxxxxxxx
 
/*
   7
  / \
 4   8
*/

From top to bottom, notice that 7 is between 4 and 8, as the structure follows the normal properties of a BST. We can express that idea with this conditional: if we encounter a node between node1 and node2, it means that it is a common ancestor of node1 and node2.

It also spawns these two ideas: if we encounter a node greater than both the nodes, we're going to find our lowest common ancestor on its left side. Likewise, if we encounter a node smaller than both the nodes, we're going to find our lowest common ancestor on its right side.

Why is that? Let's see the tree expanded a bit.

xxxxxxxxxx
 
/*
      7
     / \
    4   8
   / \
  1  5
*/

We'd like to find the LCA of 1 and 8. So start from 7, and compare 7 to 1 (greater) and 8 (less). It's in between, so we know it's the LCA!

What if we were looking to find the LCA of 1 and 5 instead?. Starting from 7, if we compare 7 to 1, it's greater. But 7 is ALSO greater than 5 -- it's greater than both.

That indicates that, from 7, we want to traverse left since we're currently to the right of both nodes.

xxxxxxxxxx
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
​
def least_common_ancestor(root, node_1, node_2):
    if root.val > node_1 and root.val > node_2:
        return least_common_ancestor(root.left, node_1, node_2)
    elif root.val < node_1 and root.val < node_2:
        return least_common_ancestor(root.right, node_1, node_2)
    else:
        return root
​
if __name__ == "__main__":
    root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(9)
    print(least_common_ancestor(root, 2, 8).val)

Here's how you could test out the previous code using another example input:

xxxxxxxxxx
 
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
​
def least_common_ancestor(root, node_1, node_2):
    if root.val > node_1 and root.val > node_2:
      return least_common_ancestor(root.left, node_1, node_2)
    elif root.val < node_1 and root.val < node_2:
      return least_common_ancestor(root.right, node_1, node_2)
    else:
        return root
​
#       7
#      / \
#     4   8
#    / \
#   1  5
​
root = Node(7)
root.left = Node(4)
root.left.left = Node(1)
root.left.right = Node(5)
root.right = Node(8)
​
print(least_common_ancestor(root, 1, 8).val)

We can alternatively use an iterative approach.

Try this exercise. Could you figure out the right sequence for this list?

Can you put these steps in the right order to iteratively find lowest common ancestor of two BST nodes?

Press the below buttons in the order in which they should occur. Click on them again to un-select.

Options:

Pre-order DFS traversal through both trees to get paths from node1 and node2
Instantiate two arrays
At each node visit, push the path nodes to the arrays
Compare the paths to find the first different node

Let's put it all together:

xxxxxxxxxx
print(lowest_common_ancestor(root, 1, 8))
 
class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None
​
def lowest_common_ancestor(root, node1, node2):
    path1 = []
    path2 = []
​
    if not get_path(root, path1, node1) or not get_path(root, path2, node2):
        return False
​
    i = 0
    while i < len(path1) and i < len(path2):
        if path1[i] != path2[i]:
            break
        i += 1
​
    return path1[i - 1]
​
def get_path(root, path, k):
    if not root:
        return False
​
    path.append(root.val)
​
    if root.val == k:
        return True
​

One Pager Cheat Sheet

Identify the lowestCommonAncestor of two nodes by finding the common owner component in the hierarchy with an algorithmic O(n) time complexity and O(1) space complexity.
Finding the lowest common ancestor of two given nodes is as simple as tracing their paths upwards until the highest shared parent is reached.
The "lowest common ancestor" of two nodes can be found by traversing upwards from the root in a BST to find the first difference in node-to-root paths.
The binary tree has exactly one root which is the top-most node and connects to all other nodes in the tree, creating a hierarchical pyramid-like structure.
The Lowest Common Ancestor of 4 and 8 in this Binary Search Tree can be easily identified.
If we traverse a BST and encounter a node between two other nodes, it is the lowest common ancestor of those two nodes, and whichever side its value is on will reveal which side of it the lowest common ancestor is found.
We can find the Lowest Common Ancestor of two nodes by comparing the node we're on to the nodes we're looking for, and traversing left or right accordingly to get closer to the LCA.
Run previous code with sample data to verify results.
An iterative approach can be used alternatively.
By using Pre-order DFS traversal to populate two arrays with the paths from each node to the root, the first different node in the paths can be easily identified as the Lowest Common Ancestor of the two nodes.
Creating a successful marketing strategy requires an in-depth understanding of customer needs, current market trends and innovative tactics.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
    print("Nice job, 3/3 tests passed!")
 
def get_path(root, path, node_to_find):
    if root is None:
        return False
​
    path.append(root.val)
    if root.val == node_to_find:
        return True
​
    # Check if node is found in left or right sub-tree
    if (root.left != None and get_path(root.left, path, node_to_find)) or (
        root.right != None and get_path(root.right, path, node_to_find)
    ):
        return True
​
    path.pop()
    return False
​
​
def least_common_ancestor(root, node_1, node_2):
    path_arr_1 = []
    path_arr_2 = []
​
    # Get paths by passing in lists to mutate
    if not get_path(root, path_arr_1, node_1) or not get_path(root, path_arr_2, node_2):
        raise Exception("Missing path from root to node!")
​
    # Do comparison of paths
    i = 0
    while i < len(path_arr_1) and i < len(path_arr_2):
        if path_arr_1[i] != path_arr_2[i]:
            break
        i += 1

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.