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.

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)

Here's a video of us explaining the solution.

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:

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.

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

​