Binary Search Tree : Lowest Common Ancestor HackerRank Solution

You are given pointer to the root of the binary search tree and two values v1and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree.

In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3. Node 3 is the lowest node which has nodes 4 and 6 as descendants.

Function Description

Complete the function lca in the editor below. It should return a pointer to the lowest common ancestor node of the two values given.

lca has the following parameters:
- root: a pointer to the root node of a binary search tree
- v1: a node.data value
- v2: a node.data value

Input Format

The first line contains an integer, n, the number of nodes in the tree.
The second line contains n space-separated integers representing node.data values.
The third line contains two space-separated integers, v1 and v2 .

To use the test data, you will have to create the binary search tree yourself. Here on the platform, the tree will be created for you.

Sample Input

6
4 2 3 1 7 6
1 7

v1 = 1 and v2 = 7 .

Sample Output

[reference to node 4]

Explanation

LCA of 1 and 7 is 4 , the root in this case.
Return a pointer to the node.

Solution :

You can take advantage of the properties of a binary search tree to find the LCA. You have to consider 3 cases to solve this problem.

Case 1: Both v1 and v2 are on the right of the current root

In this case, you can be sure that the LCA is situated in the right subtree. Go the right child and discard the left-side of the tree.

Case 2: Both v1 and v2 are on the left of the current root

Now in this case, you can be sure that the LCA is situated in the left subtree. Discard the right subtree and go to the left child.

Case 3: V1 and v2 are on two different subtrees or one of them is the current root.

This is the terminal case. The current root is the LCA so you don’t need to search anymore!

Time complexity is O(depth of the tree).

def lca(root , v1 , v2):
    # make sure v2 > v1
    if v1 > v2: v1, v2 = v2, v1
    # traverse until terminal
    while True:
        if v1 < root.info and v2 < root.info:
            root = root.left
        elif v1 > root.info and v2 > root.info:
            root = root.right
        else:
            return(root)