#700 - Search in a Binary Search Tree

EasyBinary Search Tree

Given the root of a BST and an integer val, find the node whose value equals val and return its subtree. If the node doesn't exist, return null.

Input	Output
root = [4,2,7,1,3], val = 2	[2,1,3]
root = [4,2,7,1,3], val = 5	null

Solution Space

Try it

/**
 * Searches for a value in a BST and returns the subtree rooted at that node.
 *
 * @param root Root of the BST
 * @param val  Value to search for
 * @returns    Subtree rooted at the found node, or null
 */
export function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  if (!root) return null;
  if (val === root.val) return root;
  return val < root.val
    ? searchBST(root.left, val)
    : searchBST(root.right, val);
}

Approach: BST binary search – compare `val` with the current node and recurse into the appropriate subtree.

Time: O(h) – where h is the tree height; O(log n) for balanced, O(n) worst case.

Space: O(h) – recursion stack (can be made O(1) with iteration).

#450 Delete Node in a BST

#399 Evaluate Division