Lowest Common Ancestor in a Binary Search Tree - Part 2: Iterative Solution - Binary Search Tree
In part 1 we've seen how to find the lowest common ancestor of two nodes in a binary search tree using a recursive solution. Since in that solution all we do is move to the left when both nodes are smaller than the current one, and move to the right when they are both greater, we can easily implement this iteratively:
Node *lca(Node *root, Node *n1, Node *n2) {
Node *curr = root;
while (true) {
int val = curr->value;
if (n1->value < val && n2->value < val) {
curr = curr->left;
} else if (n1->value > val && n2->value > val) {
curr = curr->right;
} else {
return curr;
}
}
}
Time complexity
The time complexity is O(h) (where h is the height of the tree) because every iteration of the while loop we either move to the left, or to the right, i.e. we go one level deeper in the tree, and in the worst case the two nodes are at the very bottom of the tree, so the loop will run h times. Since every run of the loop we do O(1) work, the total work will be O(h).
Space complexity
The space complexity is O(1) because our function uses a constant amount of space.