SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

BST Search Visualizer

Each comparison throws away one whole subtree, so a balanced tree is searched in O(log n) steps.

Start the BST Search simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Search for 45.
  2. Compare 45 with 50.
  3. 45 < 50, so go left.
  4. Compare 45 with 30.
  5. 45 > 30, so go right.
  6. Compare 45 with 40.
  7. 45 > 40, so go right.
  8. Reached an empty spot. 45 is not in the tree.

Try it with your own input →

BST search in Java, Python, C++, C and JavaScript

Node search(Node root, int val) {
  if (root == null) return null;
  if (val == root.val) return root;
  if (val < root.val)
    return search(root.left, val);
  return search(root.right, val);
}
def search(root, val):
    if root is None:
        return None
    if val == root.val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)
Node* search(Node* root, int val) {
  if (!root) return nullptr;
  if (val == root->val) return root;
  if (val < root->val)
    return search(root->left, val);
  return search(root->right, val);
}
struct Node* search(struct Node* root, int val) {
  if (root == NULL) return NULL;
  if (val == root->val) return root;
  if (val < root->val)
    return search(root->left, val);
  return search(root->right, val);
}
function search(root, val) {
  if (root === null) return null;
  if (val === root.val) return root;
  if (val < root.val)
    return search(root.left, val);
  return search(root.right, val);
}

In an interview

The same left/right walk solves "lowest common ancestor in a BST" and "closest value in a BST".

More trees