DSA sheet · Trees · BST pattern

Search in a Binary Search Tree

In the previous problem we built a BST. Now the tree is ready, and we have to find a value in it. This is the most basic BST operation, and almost every later BST problem (insert, delete, LCA, floor/ceil) walks the tree the same way. The key lesson: at each node, the BST rule tells you which ONE side to go to, so you never search the whole tree. The teacher solves it twice: first with recursion, then iteratively (a loop) to bring the extra space down to O(1).

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (the BST rule)
• Part A · Search with recursion (DFS)
• Part B · Search with a loop (iterative, O(1) space)
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node has a value, a left child link and a right child link. A missing child is None.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

The BST rule (what makes searching fast)

It's not enough for each child to be on the correct side of its parent. A value must also fit the limits set by every ancestor above it (parent, grandparent, up to the root). For example, in a tree with root 5, anything inside 5's left subtree must be smaller than 5, even if it's the right child of some smaller node like 2.

Because of this rule, if you're standing at a node and the value you want is smaller than it, the value can only be on the left side. The whole right side can be ignored. That's the trick behind this problem.

Bonus fact: the inorder of a BST is sorted

Inorder visits left subtree → node → right subtree. In a BST the left side is all smaller and the right side is all bigger, at every node, so the visit order is increasing. You can think of a BST as a sorted list folded into a tree, and searching it is just binary search on that list.

Height of a tree

The height is the number of levels, i.e. the number of nodes on the longest root-to-leaf path. We'll use it for the complexity. Call it h.

Part A · Search with recursion (DFS)

LeetCode 700 · Search in a Binary Search Tree

1The question in simple words

You get the root of a BST and a number val. Find the node whose value equals val and return that node. Returning the node means returning the whole subtree that hangs under it. If no node has that value, return None.

The tree used in the video:

          4
        /   \
       2     7
      / \
     1   3

• val = 2 → return the node 2, i.e. the subtree 2 → (1, 3).
• val = 3 → return the node 3 (a leaf, so just 3).
• val = 8 → not in the tree → return None.

2What the constraints tell us

• Number of nodes: 1 to 5000. The tree is never empty at the start. But as we move down we can still reach a None child, so the code must still handle None.
• Node values and val: up to 10⁷. Why does the teacher read this? If we had to add or multiply values, numbers like 10⁷ added many times could go past 10⁹, the int limit in Java/C++, and we'd need long. Here we only compare values. Nothing grows, so 10⁷ is completely safe. (Python never overflows anyway.)
• The values are unique in a BST, so there is at most one match.

3Intuition: how to think about it

Think of the number-guessing game: "I'm thinking of a number." You guess 50. "Smaller." You never check 51–100 again. Each answer throws away a whole range.

A BST works the same way. At each node you compare:

• equal → found it, stop.
• the value you want is smaller than the node → it can only be in the left subtree. Forget the right side.
• the value you want is bigger → it can only be in the right subtree. Forget the left side.

So we walk down one single path from the root, never both sides.

4Building the conditions from examples

Search for 2: what do we check first?

We're at the root 4. The natural first thought: "does 4 match 2?" But the teacher stops here: before reading the value, make sure the node exists. If the node is None, reading .val crashes.

Rule 2: the node matches

If the node exists and its value equals val, we found the answer. No need to look at its children: return this node right away.

Both rules return root, so the teacher joins them into one line:

if root is None or root.val == val:
    return root

Rule 3: no match → which side?

At root 4, 4 ≠ 2. Should we search both children? No. 2 is smaller than 4, and by the BST rule everything smaller than 4 is on its left. So 2 can only be on the left, if it exists at all.

For val = 3, at node 2: is 2 > 3? No → so 3 isn't on the left of 2, it must be on the right. Go to root.right.

What do we do with the answer from the child call? Just return it

When the call on 2 finds the node, it returns it to the call on 4. What should 4 do with it? Nothing except pass it up: "my child found it, so here is the answer". No combining, no attaching. So we write return self.searchBST(...) directly, with no variable in between.

5Approach steps

1. If the node is None or its value equals val → return the node.
2. If the node's value is bigger than val → return the search result from the left child.
3. Otherwise → return the search result from the right child.

6Code (Python)

class Solution:
    def searchBST(self, root, val):
        if root is None or root.val == val:      # not found here / found it
            return root
        if root.val > val:                       # val is smaller -> left side only
            return self.searchBST(root.left, val)
        return self.searchBST(root.right, val)   # val is bigger -> right side only

The last line doesn't need an else: if the if above was true, we already returned.

7Code line by line

8Dry run using the call stack

Search for 2 in the tree 4 → (2 → (1, 3), 7):

1. Call (4, 2): 4 exists, 4 ≠ 2. Is 4 > 2? Yes → go left. (4,2) waits on the stack.
2. Call (2, 2): 2 exists, 2 == 2 → found, return node 2.
3. (4, 2) gets node 2 and simply returns it. Final answer: the subtree 2 → (1, 3) ✓

Search for 3:

1. (4, 3): 4 > 3 → go left.
2. (2, 3): 2 ≠ 3. Is 2 > 3? No → go right.
3. (3, 3): match → return node 3.
4. (2, 3) passes 3 up → (4, 3) passes 3 up. Final answer: node 3 ✓

Search for 8 (not in the tree): 4 < 8 → right → 7 < 8 → right → 7 has no right child → None → None travels back up. Answer: None ✓

Notice: when searching for 2 we never looked at 7, 1 or 3. When searching for 3 we never looked at 7 or 1.

9Complexity & remember

The teacher's reasoning for time: we do not visit every node. In a full, balanced tree, the first step throws away half the nodes, the next throws away half of what's left, then half again: ½, ¼, ⅛ … That halving takes about log₂ n steps. Put another way, we touch one node per level, so the work equals the number of levels, the height.

• Time O(h): one node per level. For a balanced tree h ≈ log n, so O(log n).
• Space O(h): the recursion stack holds one call per level on the path, so also O(log n) for a balanced tree.

  1
   \
    2
     \
      3
       \
        4
         \
          5      search 5 → visits all 5 nodes

Here h = n, so the worst case is O(n) time and O(n) stack. The safe way to say it in an interview: "O(h), which is O(log n) for a balanced BST and O(n) in the worst case."

Part B · Search with a loop (iterative)

1The question

Same question as Part A. The follow-up the teacher asks: can the space be O(1)? The O(h) space in Part A comes only from the recursion stack. If we don't make recursive calls, that space goes away.

2Constraints

Same as Part A: at least 1 node, values only compared, so no overflow worries.

3Intuition

In Part A each call did a comparison and then handed over to one child, and the parent did nothing afterwards except pass the answer up. Nothing needs to be remembered on the way back. So instead of calling a function for the child, we can just move a pointer to the child and repeat, like walking down the tree with one finger.

4Building the conditions

• When does the loop stop? Take val = 8: 4 → 7 → 7's right child, which is None. We've fallen off the tree, so stop. So we keep going while root is not None.
• Inside the loop, check the match first. If root.val == val, return root right away.
• Otherwise move one step. If root.val > val (e.g. 4 > 3), the value is on the left → root = root.left. Otherwise (e.g. looking for 7 from 4) → root = root.right.
• After the loop: we only get here if we fell off the tree without a match → return None.

5Approach steps

1. While root is not None:
2. if root.val == val → return root.
3. else if root.val > val → root = root.left.
4. else → root = root.right.
5. After the loop → return None (not found).

6Code (Python)

class Solution:
    def searchBST(self, root, val):
        while root is not None:
            if root.val == val:          # found it
                return root
            if root.val > val:           # val is smaller -> step left
                root = root.left
            else:                        # val is bigger -> step right
                root = root.right
        return None                      # fell off the tree: not found

7Code line by line

8Dry run (hand table)

Tree 4 → (2 → (1, 3), 7).

Only one variable was used the whole time, no stack of waiting calls.

9Complexity & remember

• Time O(h), the same as recursion: we still visit one node per level and ignore the other half each time. O(log n) when balanced, O(n) for a straight-line tree.
• Space O(1): just the one pointer. This is the space-optimised version. On LeetCode both versions run in about the same time. The win is only memory.

Part C · Revision page

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
s = Solution()
n = s.searchBST(root, 2)
print(n.val, n.left.val, n.right.val)   # 2 1 3
print(s.searchBST(root, 3).val)         # 3
print(s.searchBST(root, 8))             # None
print(s.searchBST(TreeNode(5), 5).val)  # 5

Based on this video: Search in a Binary Search Tree