Search in BST 15 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

Given the root of a BST and a value val, find the node with that value and return its subtree. If it doesn't exist, return None.

#       4
#      / \
#     2   7
#    / \
#   1   3
# search(root, 2) → returns node 2 (with subtree [1,2,3])
# search(root, 5) → returns None

BST search is like binary search on a sorted array — at each step you eliminate half the tree:

If val < node.val → search left subtree
If val > node.val → search right subtree
If val == node.val → found it! Return the node
Time: O(h) where h = height. O(log n) average, O(n) worst case (skewed tree)

📋 Instructions

Implement `search_bst(root, val)` both recursively and iteratively. Return the found node's value (or None). Test with val=2 and val=5.

Recursive: base case is None → return None. Compare val with root.val and recurse left or right. Iterative: while root, go left or right based on comparison.

🧪 Test Cases

Input

subtree_values(result1)

Expected

[1, 2, 3]

Test case 1

Input

result2

Expected

None

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›