I am tracing part of a code given by the professor but I don't understand how the binary tree is working. The question is: "Write a function to find the lowest common ancestor in a binary search tree and return a pointer. Lowest common ancestor between two nodes a and b in tree T is defined as the lowest node in T that has both a and b as descendants. Consider the following tree as an example. the lowest common ancestor of 4 and 8 is 6. lowest common ancestor of 4 and 14 is 10."
10
6 14
4 8 12 16
My question is I don't understand how it is looping?
node *lca(node *ptr, int a, int b)
{
if(ptr==NULL)
return NULL;
while (ptr != NULL)
{
if (ptr->key >= a && ptr->key <= b)//What's key?
return (ptr);
else if (ptr->key > b)
ptr = ptr->left;
else if (ptr->key < a)
ptr = ptr->right;
}
return (ptr);
}
The idea of this code is as follow:
Assuming the tree is binary sorted, we can check if the a and b element are on different side of the current node (if the are we found our lca).
In binary tree, for each node, the bigger element going right and the small ones left. So, if ais smaller from current node and b is bigger, its mean they are from different side -> lca.
The ptr->key is accessing the data in the node.
When the first if statement fails it mean both a and b are from the same side -> the next 2 if statement choose if the continue the search right or left (is b smaller then current node both at the left side and if a bigger then current both on the right side)
Notice this code assume that a is smaller than b.