The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Tree

Problem :-
Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree.
LCA of two nodes x and y in a BST is the lowest node in the tree which contain both x and y as descendants.
For the Binary Search Tree shown below, LCA of nodes 2 and 20 is 15 .
Similarly, LCA of nodes 5 and 30 is 25 .

LCA of two nodes in a BST

Solution :-
Suppose we want to find the LCA of two nodes x and y.
We will recursively traverse the BST and try to find the first node P whose value lies between x and y i.e
( x->data < P->data < y->data ) or ( y->data < P->data < x->data ). P is the LCA.
We start at root node R. R is the LCA if any of the following conditions are satisfied :
If R -> left == x or R -> left == y
If R -> right == x or R -> right == y .
If x < R < y or y < R < x
If value of R is greater than value of both the nodes, then the LCA lies in left subtree of R and if R's value is less than value of both the nodes, the the LCA lies in right subtree of R .
See the implementation below.

#include<iostream>
using namespace std;

// node structure
typedef struct tree_node
{
   int value;
   struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
   node *new_node = new node;
   new_node->value = value;
   new_node->left = NULL;
   new_node->right = NULL;
   return new_node;
}

// create the tree
node *createTree() {
   node *root = getNewNode(25);
   root->left = getNewNode(15);
   root->right = getNewNode(30);
   root->left->left = getNewNode(5);
   root->left->right = getNewNode(20);
   root->left->left->left = getNewNode(2);
   root->right->right = getNewNode(40);
   return root;
}

//computes the LCA
//assumes both the values are present in the tree
int findLCA(node *root, int n1, int n2) {
   if (root == NULL || root->value == n1 || root->value == n2)
      return -1; //no LCA
   if (root->left != NULL && root->left->value == n1 || root->left->value == n2)
      return root->value; // current root is the LCA
   if (root->right != NULL && root->right->value == n1 || root->right->value == n2)
      return root->value; // current root is the LCA
   if ((root->value > n1 && root->value < n2) ||
         		(root->value > n2 && root->value < n1))
      return root->value; // current root is the LCA
   if (root->value > n1 && root->value > n2)
      return findLCA(root->left,n1,n2); // LCA is present in left subtree
   else
      return findLCA(root->right,n1,n2); // LCA is present in right subtree   
}

//main
int main() {
   node *root = createTree();
   int n1 = 5, n2 = 30;
   int lca = findLCA(root,n1,n2);
   cout<<"\nLCA of "<<n1<<" & "<<n2<<" is "<<lca;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Trees
* Implement the inorder , preorder and postorder traversal mechanisms of a tree
* Implement an algorithm to insert a node in a Binary Search Tree ( BST )
* Implement an algorithm to find the height of a Binary Tree
* Implement an algorithm to get the level of a node in a Binary Tree assuming root node to be at level 1
* Get the root to leaf path in a Binary Tree such that the sum of the node values in that path is minimum among all possible root to leaf paths
* Print all the ancestors of a given node in a Binary Tree
* Replace all the node values with the sum of the node values of ancestral nodes in a Binary Tree
* Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree
* Given a Binary Tree, create another tree which is a mirror image of the given tree
* Construct a tree, given its inorder and preorder traversals
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Search Tree
* Find the Least Common Ancestor ( LCA ) of two nodes in a Binary Tree
* Compute the Diameter of a given Binary Tree
* Check if a given tree is a Binary Search Tree ( BST )