DSA sheet · Trees · Binary Search Tree pattern

Predecessor & Successor in BST

Given a BST and a number key, find the value just below the key and the value just above it. The teacher starts with the obvious brute force (inorder gives a sorted list, then scan it), and then shows how to spot that it isn't the best: a BST lets you throw away half the tree at every step, and you shouldn't need to store everything. That leads to an O(height) walk from the root with O(1) extra space. She also shows the recursive version and explains why the loop version is better. Along the way you'll see a case she discovers only by testing (the key itself is in the tree), which is a good lesson in how real code gets written.

Every part 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
• Part A · Brute force: inorder list + scan
• Part B · Optimal: walk down the BST (iterative)
• Part C · The same walk with recursion
• Part D · Revision page

Part 0 · Before starting

What is a tree node?

Each node holds a value, a left child link and a right child link; a missing child is None. (On GFG the value field is called data; we use val to match the other pages.)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The BST rule

In a binary search tree, for every node, all values in its left subtree (the left child and everything under it) are smaller, and all values in its right subtree are bigger. This is about all the nodes below, not only the children.

        50
      /    \
    30      70
   /  \    /  \
  20  40  60   80

        50
      /    \
    30      70
   /  \
  20  55

55 is fine under 30 (55 > 30), but it lives in 50's left subtree, and 55 > 50. Broken.

Why inorder of a BST is sorted

Inorder = left subtree, then node, then right subtree. Everything on the left is smaller and everything on the right is bigger, so each node lands exactly between them, at every level. Result: values in increasing order. For the valid tree above: 20 30 40 50 60 70 80.

The two words in the title

• Predecessor of key = the largest value that is smaller than key (the one just before it in sorted order).
• Successor of key = the smallest value that is bigger than key (the one just after it).

Two helper facts: the maximum of a subtree is reached by going right until you can't; the minimum by going left until you can't.

Part A · Brute force: inorder list + scan

GFG: Predecessor and Successor

1The question in simple words

You get the root of a BST and an integer key. Return two nodes: the predecessor (largest value < key) and the successor (smallest value > key). If one of them doesn't exist, return None in its place.

Important: the key may or may not be in the tree. Both situations must work.

        50
      /    \
    30      70
   /  \    /  \
  20  40  60   80

      8
     / \
    1   9
     \   \
      4   10
     /
    3

In Example 2 the key is the root. The value just below 8 is 4 (sorted: 1 3 4 8 9 10), and the value just above is 9.

2What the constraints tell us

• Number of nodes: 1 to 10⁵ → the root always exists.
• n can be 10⁵, so an O(n²) idea is 10¹⁰ operations, far beyond the ~10⁸ limit → TLE. So even the brute force must be better than n². Linear is fine.
• Values are small integers, compared only, so plain int is fine.

3Intuition

The teacher's first reminder: since this is a BST, don't think of sorting. Inorder already gives you a sorted list. Once the values are in order, "just below the key" and "just above the key" are easy to read off by scanning.

4Building the scan from Example 1

Inorder list for Example 1: 20 30 40 50 60 70 80, key = 65. Walk from left to right:

• 20 < 65 → it could be the predecessor. Not sure yet, because a closer smaller value may come later. Save it: pre = 20.
• 30 < 65 → closer, pre = 30. Then 40 → pre = 40, 50 → pre = 50, 60 → pre = 60.
• 70 > 65 → this is the first value bigger than the key. That makes it the smallest bigger value → suc = 70. Stop.

5Approach steps

1. Do an inorder traversal and collect the nodes in a list (sorted by value).
2. Set pre = None, suc = None.
3. For each node in order: if its value < key → pre = node. If its value > key → suc = node and stop. If equal → skip.
4. Return [pre, suc].

6Code (Python)

class Solution:
    def findPreSuc(self, root, key):
        nodes = []
        self.inorder(root, nodes)                # sorted by value

        pre = suc = None
        for node in nodes:
            if node.val < key:
                pre = node                       # a closer smaller value
            elif node.val > key:                 # FIX: skip node.val == key
                suc = node                       # first bigger value
                break
        return [pre, suc]

    def inorder(self, node, nodes):
        if node is None:
            return
        self.inorder(node.left, nodes)
        nodes.append(node)
        self.inorder(node.right, nodes)

7Code line by line

8Dry run (hand table)

Example 2, key = 8. Inorder: 1 3 4 8 9 10.

Answer [4, 9] ✓. (With the video's plain else, the 8 row would have given suc = 8.)

9Complexity & remember

• Time O(n) + O(n) = O(2n) = O(n): one pass to build the list, one pass to scan it.
• Space O(n) for the list, plus O(h) for the inorder recursion stack (h = height).

Linear, so it is acceptable, and fine to say in an interview as a first answer. But it isn't the best. The teacher gives two hints to tell:

1. Time hint: it's a BST and we're searching for a value near the key. In a BST you can go left and ignore the right side, or go right and ignore the left side. That kind of halving gives log n, much smaller than n.
2. Space hint: we stored every node in an extra list. Ask: can we get the answer while walking through the tree, without storing anything?

Part B · Optimal: walk down the BST (iterative)

Same question and constraints as Part A.

3Intuition: carry two "best so far" notes as you walk

Walk from the root down, like searching for the key. At each node, compare it with the key:

• node < key → it's a candidate predecessor. Write it down. A closer one can only be bigger than this node, and bigger values are on its right. So go right and forget its left side.
• node > key → it's a candidate successor. Write it down. A closer one can only be smaller, so go left and forget its right side.

Each step drops half of what's left, which is why this is one node per level → O(height).

4Building the conditions from Example 1 (key = 65)

At 50: smaller than the key

50 < 65, so 50 can be the predecessor. Save pre = 50. Should we look left or right for something closer? Left of 50 are 20, 30, 40, all smaller than 50, so further from 65. Only the right side can hold something between 50 and 65. Go right; the whole left half is ignored.

At 70: bigger than the key

70 > 65, so 70 can't be the predecessor, but it can be the successor. Save suc = 70. A closer successor would be smaller than 70 but still above 65, so it could only be in 70's left side. Going right (80) would only get worse. Go left.

At 60: smaller again, and why it beats 50

60 < 65 → update pre = 60. How do we know 60 is closer than 50 without comparing them? Because we reached 60 by going right from 50. By the BST rule, everything in 50's right subtree is bigger than 50. So any smaller-than-key value we find down here is automatically closer than 50. The newest candidate is always the best one so far, and we can overwrite without checking.

Then go right again. Why? There might still be something like 61, 62, 63 or 64 below:

        50
      /    \
    30      70
           /
         60
           \
            61   ← if this existed, pre would become 61
              \
               64  ← and then 64

In the real tree, 60's right is None, so the loop ends. Answer: pre = 60, suc = 70 ✓.

The case found only by testing: the key is in the tree

The teacher's tip here: you don't write the full code in one go. Write what you understood, run it, and when a test fails, dry-run that test to see which scenario you missed. Here, try key = 50. At the root, 50 is not < 50 and not > 50, so neither rule fires. With only two rules, the loop would never move (stuck forever). We need a third branch for equal.

When the node equals the key:

• The nearest smaller value is the largest value in its left subtree: go left once, then right as far as possible. For 50: 30 → 40 → no right child → pre = 40.
• The nearest bigger value is the smallest value in its right subtree: go right once, then left as far as possible. For 50: 70 → 60 → no left child → suc = 60.
• Check that the left / right child exists before walking into it.
• Then break: nothing further down or elsewhere can be closer, so we're done.

Why iterative and not recursive?

We only ever go down one path, so we don't need recursion to "come back". A simple cur = cur.left / cur = cur.right in a while loop does it. Recursion would do the same steps but keep one waiting call per level on the stack, costing O(h) extra space. The loop uses O(1). If an iterative way is possible, prefer it.

5Approach steps

1. pre = None, suc = None, cur = root (use cur so we don't lose root).
2. While cur is not None:
3. • cur.val < key → pre = cur, move right.
4. • cur.val > key → suc = cur, move left.
5. • equal → max of left subtree becomes pre (if left exists), min of right subtree becomes suc (if right exists), break.
6. Return [pre, suc].

6Code (Python)

class Solution:
    def findPreSuc(self, root, key):
        pre = suc = None
        cur = root
        while cur is not None:
            if cur.val < key:                    # candidate predecessor
                pre = cur
                cur = cur.right                  # look for a closer (bigger) one
            elif cur.val > key:                  # candidate successor
                suc = cur
                cur = cur.left                   # look for a closer (smaller) one
            else:                                # found the key itself
                if cur.left is not None:
                    temp = cur.left
                    while temp.right is not None:
                        temp = temp.right        # max of left subtree
                    pre = temp
                if cur.right is not None:
                    temp = cur.right
                    while temp.left is not None:
                        temp = temp.left         # min of right subtree
                    suc = temp
                break
        return [pre, suc]

7Code line by line

8Dry run

Key = 65 (not in the tree)

Key = 50 (found at the root)

Example 2, key = 8

9Complexity & remember

• Time O(h). Key not found: one node per level on the way down. Key found: the way down, then one chain into the left subtree and one into the right. The teacher counts the worst case as log n for the predecessor chain plus log n for the successor chain, 2 log n, which is still O(log n) for a balanced tree. For a skewed tree (a straight line), h = n, so the worst case is O(n).
• Space O(1): only a few pointers, no stack, no list.

Part C · The same walk with recursion

The teacher also shows a recursive version "just to show you". Steps ① to ④ are identical to Part B; only the way we move changes.

5What changes

1. Keep a result list res = [None, None]: index 0 is the predecessor, index 1 the successor. The helper fills it in.
2. Base case: node is None → return. (The teacher forgot this at first and added it, so watch for it.)
3. Smaller → res[0] = node, recurse on the right. Bigger → res[1] = node, recurse on the left.
4. Equal → max of left into res[0], min of right into res[1]. No break needed: we just don't make another call, so the recursion returns by itself.

6Code (Python)

class Solution:
    def findPreSuc(self, root, key):
        res = [None, None]                       # [predecessor, successor]
        self.helper(root, key, res)
        return res

    def helper(self, node, key, res):
        if node is None:                         # base case
            return
        if node.val < key:
            res[0] = node
            self.helper(node.right, key, res)
        elif node.val > key:
            res[1] = node
            self.helper(node.left, key, res)
        else:
            if node.left is not None:
                temp = node.left
                while temp.right is not None:
                    temp = temp.right
                res[0] = temp
            if node.right is not None:
                temp = node.right
                while temp.left is not None:
                    temp = temp.left
                res[1] = temp

7Code line by line (the differences)

8Dry run (key = 65)

Same moves as the table in Part B, and the same answer [60, 70]. The difference: four calls were waiting on the stack at once.

9Complexity

• Time O(h), same as iterative: one call per level.
• Space O(h): one stack frame per level. O(log n) if balanced, O(n) if skewed. That's why the loop version is preferred.

Part D · Revision page

t1 = TreeNode(50, TreeNode(30, TreeNode(20), TreeNode(40)),
                  TreeNode(70, TreeNode(60), TreeNode(80)))
t2 = TreeNode(8, TreeNode(1, None, TreeNode(4, TreeNode(3))),
                 TreeNode(9, None, TreeNode(10)))
s = Solution()
def show(pair): return [n.val if n else None for n in pair]
print(show(s.findPreSuc(t1, 65)))   # [60, 70]
print(show(s.findPreSuc(t1, 50)))   # [40, 60]
print(show(s.findPreSuc(t1, 60)))   # [50, 70]
print(show(s.findPreSuc(t2, 8)))    # [4, 9]
print(show(s.findPreSuc(t1, 10)))   # [None, 20]
print(show(s.findPreSuc(t1, 80)))   # [70, None]

Based on this video: Inorder Predecessor and Successor in BST