Search a Binary Search Tree

easy bst tree

Problem

Given the root of a BST and a value v, return the subtree rooted at the matching node, or null if not found. Walk down the tree comparing v to each node and going left or right.

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;
}

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