Least Common Ancestor in Binary Search Tree

In this class, We discuss the Least Common Ancestor in Binary Search Tree.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary search tree and two node values.

Our task is to identify the least common ancestor of the two nodes.

The below diagram shows the least common ancestor example.

Time complexity: O(H)

Space complexity: O(H)

H is the height of the binary search tree

Logic:

Use the properties of the binary search tree.

From the example, the first node value is ten. The .value 10 is less than both 17 and 35.

The ancestor of 10 and 35 will be on the right side of the root node.

Similarly, take nodes 2 and 8.

The root node 10 is greater than both 2 and 8.

The ancestor of 2 and 8 will be on the left side of the root node.

We use the above conditions are used to identify the ancestor.

We provide a step-by-step explanation in the video.

Code:

class Node:

    # Constructor to create a new node

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def LCA(root, n1, n2):

    #code here.

    while root:

        if root.data > n1 and root.data > n2:

            root = root.left

        elif root.data < n1 and root.data < n2:

            root = root.right

        else:

            break

    return root

if __name__ == ‘__main__’:

    root = Node(10)

    root.left = Node(5)

    root.right = Node(18)

    root.left.left = Node(2)

    root.left.right = Node(8)

    root.right.left = Node(15)

    root.right.right = Node(25)

    root.right.left.right = Node(17)

    root.right.right.right = Node(35)

    n1=17

    n2=35

    print(“Least Common Ancestor”)

    z=LCA(root,n1,n2)

    if(z!=None):

        print(z.data)

    else:

        print(“Numbers not in Bst “)