Search in a Binary Search Tree

easy bst tree

Problem

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Inputtree (level-order BST) = [4, 2, 7, 1, 3, _, 9], v = 3

Outputnode 3

From 4: 3 < 4 → left to 2. 3 > 2 → right to 3. Match.

BST (level-order)

def search_bst(root, v):
    n = root
    while n:
        if n.val == v: return n
        n = n.left if v < n.val else n.right
    return None

function searchBST(root, v) {
  let n = root;
  while (n) {
    if (n.val === v) return n;
    n = v < n.val ? n.left : n.right;
  }
  return null;
}

class Solution {
    public TreeNode searchBST(TreeNode root, int v) {
        TreeNode n = root;
        while (n != null) {
            if (n.val == v) return n;
            n = v < n.val ? n.left : n.right;
        }
        return null;
    }
}

TreeNode* searchBST(TreeNode* root, int v) {
    TreeNode* n = root;
    while (n) {
        if (n->val == v) return n;
        n = v < n->val ? n->left : n->right;
    }
    return nullptr;
}

Explanation

Searching a BST is like a guessing game where every comparison cuts the remaining search in half. We never wander into branches that can't possibly hold our target.

Starting at the root with pointer n, we compare v to n.val. If they're equal, we found the node and return it. If v < n.val, the target can only be in the left subtree (smaller values), so n = n.left. Otherwise it's in the right subtree, so n = n.right.

We keep looping until we either match or fall off the tree (n becomes null), in which case the value isn't present and we return null.

Example: BST [4, 2, 7, 1, 3, _, 9], target 3. At 4: 3 < 4, go left to 2. At 2: 3 > 2, go right to 3. Match — return that node.

Because each step drops one level, the work is proportional to the tree's height, and it uses only a single pointer.

Time: O(h) Space: O(1)