Find Node in Binary Search Tree - Part 1: Recursive Solution - Binary Search Tree

In this article, we will see how to find the node with a given key in a binary search tree, using a recursive solution. The binary search tree property (i.e. that for each node, everything in the left subtree has a smaller key, and everything in the right subtree has a larger key) makes it easy to search for a given key efficiently. The idea is to start at the root of the tree, and check if the key we're looking for is equal to the key of root, if that's the case, we found the node. Else we check if the key we're looking for is smaller than the key of root, and in that case, if the node with that key is present at all, it must be in the left subtree, so we recursively look for the key in the left subtree. Otherwise, the key is greater than the key of root, so it must be in the right subtree, if present at all, so we recursively look for the key in the right subtree.

With that in mind, here's the function that tries to find the node with a given key in a binary search tree, and returns that node, or returns null if there is no node with such key.

Node *findNode(Node *root, int key) {
  if (root == nullptr) return nullptr;

  if (key == root->key) {
    return root;
  } else if (key < root->key) {
    return findNode(root->left, key);
  } else {
    return findNode(root->right, key);
  }
}

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 there will be as many calls as the height of the tree (since each function call we're going one level deeper in the tree), and we're doing O(1) work in each call, which means that the total work for all the calls is O(h). If the binary search tree is balanced, this would be O(log n).

Space complexity

The space complexity is O(h) (where h is the height of the tree) because this is a function that calls itself recursively, so the call stack grows with each call, and in the worst case there will be as many calls as the height of the tree, which means that the space taken is O(h). If the binary search tree is balanced, this would be O(log n).

Video with explanation