DSA sheet · Binary Search Tree · search pattern

Closest Node in a BST

Given a BST and a number k, find how close the tree can get to k: the smallest absolute difference between k and any node's value. The teacher starts with the obvious plan (write the tree out in sorted order with inorder, then binary search the array), shows that the extra array is a waste, and then does the binary search directly on the tree, walking one path from the root with a simple while loop. That's O(h) time and O(1) space. It's the same "follow the signpost" move as Search in a BST, plus one variable that remembers the best difference so far.

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 into an array, then binary search
• Part B · Optimal: walk down the tree, keep the best difference
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

A node holds a value and links to its left and right children (None if missing).

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, at every node: all values in the left subtree (the left child and everything below it) are smaller than the node, and all values in the right subtree are bigger. Short form: left subtree < node < right subtree. It has to hold for all nodes below, not just the direct children.

This is the tree the teacher uses (the lower part is drawn to match her inorder list):

          10
         /  \
        2    11
       / \
      1   5
         / \
        3   6
         \
          4

Check node 10: everything on the left (2, 1, 5, 3, 6, 4) is smaller, and 11 on the right is bigger. Check node 2: 1 is smaller, and 5, 3, 6, 4 are all bigger. Check node 5: 3 and 4 are smaller, 6 is bigger.

Why inorder of a BST gives a sorted list

Inorder traversal = visit the left subtree, then the node, then the right subtree. At every node, everything printed before it came from its left (smaller) and everything after it comes from its right (bigger). Since that's true at every level, the whole printout is in increasing order. For our tree: 1 2 3 4 5 6 10 11. We never sorted anything; the BST shape did it for us. Part A relies on this.

Absolute difference

The absolute difference between a and b is the distance between them on the number line, ignoring the sign: abs(a − b). abs(12 − 13) = 1 and abs(14 − 13) = 1. So a value below k and a value above k can be equally close.

Part A · Brute force: inorder into an array, then binary search

GFG · Find the closest element in BST (minDiff(root, K))

1The question in simple words

You get the root of a BST and an integer k. Over all nodes, find the smallest value of abs(node.val − k) and return that number (the difference, not the node).

• k = 13 → the closest value is 11 → answer 2.
• k = 7 → the closest value is 6 → answer 1.
• k = 6 or k = 5 → that value is in the tree → answer 0.

The teacher's point: "closest" doesn't mean "just below" or "just above". For k = 13, both 12 and 14 would be distance 1. We want whichever number is nearest, on either side. That's why the problem is called "closest".

2What the constraints tell us

• Up to 10⁵ nodes. O(n²) would be 10¹⁰ operations, far past the ~10⁸ limit → certain TLE. So we need O(n) or better.
• Because it's a BST, we can hope for O(log n) on a balanced tree, like binary search.

3Intuition

A sorted list makes "find the closest number" easy with binary search. And Part 0 told us inorder gives us a sorted list for free. So: flatten the tree with inorder, then binary search the list, remembering the smallest difference seen along the way.

4Building the logic from the example

Array [1, 2, 3, 4, 5, 6, 10, 11], k = 13. Look at the middle element:

• If it equals k → the difference is 0, which can't be beaten → return 0.
• If it's smaller than k: everything to its left is even smaller, so even farther from k. Only the right half can get closer → move right.
• If it's bigger than k: by the same logic, only the left half can get closer → move left.
• At every middle element, save the difference if it's the smallest so far. When the two ends cross, the saved number is the answer.

5Approach steps

1. Do an inorder traversal and put every value into a list (it comes out sorted).
2. Binary search with lo = 0, hi = len − 1, and best = ∞.
3. At each mid: update best with abs(arr[mid] − k). If equal → return 0. If smaller than k → lo = mid + 1, else hi = mid − 1.
4. When lo passes hi → return best.

6Code (Python)

class Solution:
    def minDiff(self, root, k):
        arr = []
        self.inorder(root, arr)            # sorted, because it's a BST

        best = float('inf')
        lo, hi = 0, len(arr) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            best = min(best, abs(arr[mid] - k))
            if arr[mid] == k:
                return 0
            if arr[mid] < k:
                lo = mid + 1                # need a bigger number
            else:
                hi = mid - 1                # need a smaller number
        return best

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

7Code line by line

8Dry run (k = 13)

9Complexity & remember

• Time O(n) + O(log n) = O(n). The inorder visits all n nodes; the binary search adds only log n. When we add costs, the bigger one wins, so we just say O(n).
• Space O(n) for the array, plus O(h) for the inorder recursion stack (one waiting call per level).

The teacher's question: did we really need to store every node? The tree is already "sorted" in its shape. We can run the same binary-search moves directly on the tree and skip the array.

Part B · Optimal: walk down the tree, keep the best difference

Same question and constraints. The steps of the binary search stay; the array goes away.

1Intuition: the tree is a binary search already

Standing at a node, it plays the role of "mid". If the node is smaller than k, a closer number can only be bigger, so it can only be in the right subtree. Forget the whole left side. If the node is bigger than k, go left. Each step drops a whole subtree, and we visit only one node per level.

On the way down, keep one outside variable, ans, holding the smallest difference seen so far.

2Why a while loop and not recursion?

A recursive walk would keep one call per level on the stack, which is O(h) space. We only ever move to one child and never need to come back, so a while loop that moves root down does the same job in O(1) space. The teacher deliberately chooses the iterative style to save that stack space.

3Building the conditions from examples

Example k = 13 → keep going right

At 10: 10 < 13. Save abs(10 − 13) = 3. A closer number must be bigger → go right. At 11: 11 < 13. Save 2 (better than 3). Go right → None. The loop ends, return 2.

Example k = 7 → left first, then right

At 10: 10 > 7, so a closer number must be smaller → go left.

What if the node equals k? (k = 10, or k = 5)

Suppose k = 10. At the root the difference is already 0. Going left or right can't do better than 0, because a distance can't be negative. So we stop and return 0 immediately.

With k = 5: at 10 save 5, go left. At 2 save 3, go right. At 5 the difference is 0 → return 0. No need to look any further.

Where do we update the answer?

The teacher puts the update at the top of the loop, right after we know the node isn't None, and before any return or move. That way every node we stand on is counted before we leave it. Safer than trying to remember to update in each branch.

4Approach steps

1. ans = ∞.
2. While root is not None:
3. Update ans = min(ans, abs(root.val − k)).
4. If root.val == k → return 0.
5. If root.val < k → root = root.right. Else → root = root.left.
6. After the loop → return ans.

5Code (Python)

class Solution:
    def minDiff(self, root, k):
        ans = float('inf')
        while root is not None:
            ans = min(ans, abs(root.val - k))   # count this node first
            if root.val == k:
                return 0                        # can't beat 0
            if root.val < k:
                root = root.right               # need a bigger number
            else:
                root = root.left                # need a smaller number
        return ans

6Code line by line

7Dry run

Run 1: k = 7 (the teacher's main example)

          10          path taken for k = 7:
         /  \           10 → 2 → 5 → 6 → None
        2    11
       / \              skipped: 11, 1, and the 3-4 branch
      1   5
         / \
        3   6
         \
          4

Run 2: k = 6 → 10 (diff 4), go left. 2 (diff 4, no change), go right. 5 (diff 1), go right. 6: diff 0, and 6 == 6 → return 0 right away.

Run 3: k = 13 → 10 (3), right. 11 (2), right. None → return 2. Only 2 nodes visited.

(In the video the teacher once says "2 is greater, go right" for k = 5. She means 2 is smaller than 5, which is why we go right.)

8Complexity

• Time O(h): one node per level. For a balanced BST that's O(log n), the fastest possible here. For a skewed BST (a straight line like 1 → 2 → 3 → …), h = n, so it becomes O(n). The teacher quotes log n, which assumes a balanced tree.
• Space O(1): just ans and root. No array, no recursion stack.

9Remember

Part C · Revision page

root = TreeNode(10,
          TreeNode(2, TreeNode(1),
                      TreeNode(5, TreeNode(3, None, TreeNode(4)), TreeNode(6))),
          TreeNode(11))
s = Solution()
print(s.minDiff(root, 13))   # 2
print(s.minDiff(root, 7))    # 1
print(s.minDiff(root, 6))    # 0
print(s.minDiff(root, 5))    # 0
print(s.minDiff(root, -4))   # 5  (closest is 1)
print(s.minDiff(TreeNode(9), 4))  # 5

Based on this video: Closest Binary Search Tree Value