Understanding the lowest common ancestor
The lowest common ancestor of two nodes in a binary tree is the lowest node from the root, with both nodes as its descendants. Either of those nodes can also be the lowest common ancestor for itself and the other node. Consider the following examples of the lowest common ancestors for a pair of nodes in a binary tree.
The lowest common ancestor of two nodes in a generic binary tree.
The generic algorithm to find the lowest common ancestor of two nodes in a binary tree uses a slightly modified version of the postorder traversal. However, we can use a drastically faster algorithm to find the lowest common ancestor for a binary search tree.
Algorithm
The binary search tree follows the special binary search property which means the value of all the nodes in the left subtree of a node is smaller than it and the value of all the nodes in the right subtree is greater.
Liking the course? Check our discounted plans to continue learning.