Learn basic concept of c , c++ and python programming in regularcodes.com
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.
View linked list insertion process.
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.
Note that not given all step of execution process here.View How to insert Linked list node and so on.