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

# Algorithms

## 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 .

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.