Algorithmathon Day 11: Binary Search Tree Lowest Common AncestorCreated: 25 July 2013 Modified:
The Lowest Common Ancestor (LCA) is the node furthest down the tree that is an ancestor of two other nodes. In the tree depicted below the LCA of child nodes 10 and 30 would be 20 and the LCA of 20 and 90 would be 50.
When we first start considering the Lowest Common Ancestor (LCA) problem it is quite natural for it to seem quite difficult. One might start considering searching for each child node while keeping an ancestor list. The better solution turns out to be quite simple. Up until now we have been writing algorithms to solve problems in spite of the data structure. This time the nature of a Binary Search Tree (BST) itself will help us solve the problem. We know that the right side numbers are the larger numbers and the left side is the smaller numbers. It turns out that the LCA will be the first node that is between our two numbers.
- Get the root node
- Find the current node value
- If both child values are less than the current node value goto step 2 with the lesser/left child node as the target
- If both child values are greater than the current node value goto step 2 with the greater/right child node as the target
- Otherwise the current node is the LCA
Armed with this knowledge we can write our tests and follow it with our code.
Tomorrow we will start String manipulation.tags: Algorithm - Algorithmathon - Binary Search Tree - RSpec - Ruby