Search in a Binary Search Tree

LeetCode 700 • Easy • Trees

Input: root = [4,2,7,1,3], val = 2 → Output: subtree rooted at 2
BST: go left if val < root.val, right if val > root.val.

TimeO(h)path height

SpaceO(1)pointer only

Current: 4

Current

Path / Found

Current

Speed:

Ready

Press Play. While root and root.val!=val: go left if val<root.val, else right. Return root.

✎ Whiteboard

Size:3

⌨ Type It — Iterative

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ SEARCH IN BST — ITERATIVE ═══

PATTERN ▸ BST traversal (left/right by val) O(h) · O(1)

① LOOP

while root and root.val != val:

root = root.left if val < root.val else root.right

② RETURN

return root

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ SEARCH IN BST — RECURSIVE ═══

PATTERN ▸ BST recursion O(h) · O(h)

① BASE CASE

if not root or root.val == val: return root

② RECURSE

return searchBST(root.left, val) if val < root.val else searchBST(root.right, val)

▼ your implementation ▼

Verify your solution: