Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

lowest common ancestor of a binary search tree

What is lowest common ancestor (LCA) of bst node. this is lowest parent node of given n1 and n2.

Assume that given n1 and n2 nodes are we finding LCA they are exist in bst. Given following example of LCA.

Find LCA of BST

View linked list insertion process.

Try it yourself

Example 1: n1=80,n2=120.


Example 2: n1=35,n2=80.


Example 3: n1=35,n2=40.


Algorithm: iterative approach.

Use one temp pointer that is assign address of root of bst. In this (while loop) check given value n1 and n2. that are exist in bst. if n1 and n2 value are biger then to temp pointer node value. then temp point assign address of temp->left.

If n1 and n2 value are smaller then assign temp pointer address of temp->right child.

Otherwise we are getting n1 and n2 lowest common ancestor.

Time complexity of this algorithm is O(n).

C program to find lowest common ancestor.


Code execution: view code execution process.

Stack Areamainroot(pointer)ancestorn1 (int) =80n2 (int) =120status (int) =1temp(pointer) Heap Areastruct Treedata (int)= 50left_child (pointer) right_child (pointer) struct Treedata (int)= 40left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 100left_child (pointer) right_child (pointer) struct Treedata (int)= 30left_child (pointer) right_child (pointer) struct Treedata (int)= 70left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 120left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 10left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 35left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 80left_child (pointer)= NULLright_child (pointer)= NULL

Note that not given all step of execution process here.View How to insert Linked list node and so on.

Try it yourself

Spread the post

Recommended Posts: