Find Node in Binary Search Tree - Part 2: Iterative Solution - Binary Search Tree
In part 1 we've seen how to search for a given key in a binary search tree using a recursive solution. This time let's look at the iterative solution.
In the recursive solution, we essentially move to the left when the key is smaller than the key of the current root (by calling the function recursively), and move to the right when it is larger. We can easily implement this process iteratively:
Node *findNode(Node *root, int key) {
Node *curr = root;
while (curr != nullptr) {
if (key == curr->key) {
return curr;
} else if (key < curr->key) {
curr = curr->left;
} else {
curr = curr->right;
}
}
return nullptr;
}
Time complexity
The time complexity is O(h) (where h is the height of the tree) because in the worst case the node we're looking for is not in the tree and we move all the way to the bottom of the tree along the longest path, and so the while loop will execute as many times as the height of the tree (since each iteration we're going one level deeper in the tree), and we're doing O(1) work each iteration, which means that the total work done by the while loop is O(h). If the binary search tree is balanced, this would be O(log n).
Space complexity
The space complexity is O(1) because we're using a constant amount of space.