LeetCode 272 - Closest Binary Search Tree Value II

This problem asks us to find the k values in a Binary Search Tree, or BST, whose values are numerically closest to a given floating point target. A BST has a very important property: - Every value in the left subtree is smaller than the current node.

leetcodehardtwo-pointersstacktreedepth-first-searchbinary-search-treeheap-(priority-queue)binary-tree

LeetCode Problem 272

Difficulty: 🔴 Hard
Topics: Two Pointers, Stack, Tree, Depth-First Search, Binary Search Tree, Heap (Priority Queue), Binary Tree

Solution

Problem Understanding

This problem asks us to find the k values in a Binary Search Tree, or BST, whose values are numerically closest to a given floating point target.

A BST has a very important property:

  • Every value in the left subtree is smaller than the current node.
  • Every value in the right subtree is larger than the current node.

This ordering allows us to avoid scanning every node in some optimized solutions.

The input consists of:

  • root, the root node of a BST
  • target, a floating point number
  • k, the number of closest values we must return

The output should contain exactly k node values from the tree whose absolute difference from target is smallest.

For example, if the target is 3.7, then:

  • 4 has distance |4 - 3.7| = 0.3
  • 3 has distance |3 - 3.7| = 0.7
  • 5 has distance 1.3

So the two closest values are [4, 3].

The problem guarantees that there is only one unique correct set of k closest values. This removes ambiguity when multiple answers could otherwise exist.

The constraints are important:

  • Up to 10^4 nodes
  • Values can be very large
  • k may be as large as n

A naive solution that sorts all nodes is acceptable for 10^4, but the follow up specifically asks whether we can do better than O(n) for balanced BSTs.

Several edge cases are important:

  • A tree with only one node
  • k = n, meaning every value must be returned
  • A target smaller than all node values
  • A target larger than all node values
  • A target exactly equal to a node value
  • Highly unbalanced trees

A naive implementation can easily fail when deciding which side of the BST to explore or when handling predecessor and successor traversal correctly.

Approaches

Brute Force Approach

The simplest solution is to traverse the entire tree and collect all node values into an array.

Once we have all values:

  1. Compute each value's distance from target
  2. Sort by absolute difference
  3. Return the first k elements

Because every node is examined, this approach is always correct. We directly compare all candidates and choose the closest ones.

However, it ignores the BST structure completely. Even though the tree is ordered, we still scan every node and perform a sort.

The complexity becomes:

  • Traversal: O(n)
  • Sorting: O(n log n)

This is slower than necessary, especially when the BST is balanced.

Optimal Approach

The key insight is that BST inorder traversal produces values in sorted order.

Instead of collecting every node and sorting afterward, we can use the BST structure to efficiently move outward from the target value.

The optimal solution uses two stacks:

  • A predecessor stack for values smaller than the target
  • A successor stack for values larger than or equal to the target

These stacks simulate two iterators:

  • One moves backward through sorted BST values
  • One moves forward through sorted BST values

At every step, we compare:

  • the closest smaller candidate
  • the closest larger candidate

Whichever is closer to the target gets added to the result.

This works similarly to merging two sorted streams around the target.

Because each stack operation follows BST paths, the runtime becomes:

  • O(log n) setup for balanced BSTs
  • O(k log n) in the worst case for extracting results

This is significantly better than traversing all nodes when k is small.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Traverse entire tree and sort by distance
Optimal O(log n + k) average, O(n) worst O(log n) average Uses BST ordering with predecessor and successor stacks

Algorithm Walkthrough

Optimal Algorithm Using Two BST Iterators

  1. Initialize two stacks, predecessors and successors.

The predecessor stack will store nodes whose values are smaller than the target. The successor stack will store nodes whose values are greater than or equal to the target. 2. Traverse the BST from the root to initialize both stacks.

While traversing:

  • If node.val < target, push the node into predecessors and move right.
  • Otherwise, push the node into successors and move left.

This effectively positions two iterators around the target. 3. Define a helper function to get the next predecessor.

The predecessor iterator behaves like reverse inorder traversal:

  • Pop the top node
  • Move to its left child
  • Then repeatedly move right while pushing nodes

This gives the next smaller BST value. 4. Define another helper function to get the next successor.

The successor iterator behaves like normal inorder traversal:

  • Pop the top node
  • Move to its right child
  • Then repeatedly move left while pushing nodes

This gives the next larger BST value. 5. Repeat k times.

At each step:

  • If one stack is empty, use the other.

  • Otherwise compare:

  • abs(predecessor - target)

  • abs(successor - target)

Choose the closer value and advance that iterator. 6. Append the selected value to the result list. 7. Return the result after collecting exactly k values.

Why it works

The BST inorder traversal produces sorted values. The predecessor stack always points to the next largest value smaller than the target, while the successor stack always points to the next smallest value larger than or equal to the target.

At every step, the closest remaining value to the target must be at the top of one of these two stacks. By always choosing the closer top element, we greedily construct the correct set of k closest values in sorted proximity order.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional

class Solution:
    def closestKValues(
        self,
        root: Optional['TreeNode'],
        target: float,
        k: int
    ) -> List[int]:

        predecessors = []
        successors = []

        def init_predecessors(node):
            while node:
                if node.val < target:
                    predecessors.append(node)
                    node = node.right
                else:
                    node = node.left

        def init_successors(node):
            while node:
                if node.val >= target:
                    successors.append(node)
                    node = node.left
                else:
                    node = node.right

        def get_predecessor():
            node = predecessors.pop()
            value = node.val

            node = node.left

            while node:
                predecessors.append(node)
                node = node.right

            return value

        def get_successor():
            node = successors.pop()
            value = node.val

            node = node.right

            while node:
                successors.append(node)
                node = node.left

            return value

        init_predecessors(root)
        init_successors(root)

        result = []

        for _ in range(k):

            if not predecessors:
                result.append(get_successor())

            elif not successors:
                result.append(get_predecessor())

            else:
                pred_diff = abs(predecessors[-1].val - target)
                succ_diff = abs(successors[-1].val - target)

                if pred_diff <= succ_diff:
                    result.append(get_predecessor())
                else:
                    result.append(get_successor())

        return result

The implementation begins by building two stacks.

The predecessor stack stores candidate nodes smaller than the target. During initialization, whenever a node value is smaller than the target, the algorithm pushes it and moves right because larger values may still remain below the target.

The successor stack stores candidate nodes greater than or equal to the target. Whenever a node qualifies, it is pushed and traversal continues left to search for even smaller valid successors.

The get_predecessor() helper simulates reverse inorder traversal. After removing the current predecessor node, it explores the left subtree and pushes all right descendants. This guarantees the next top element is the next smaller BST value.

Similarly, get_successor() simulates standard inorder traversal. After removing the current successor node, it explores the right subtree and pushes all left descendants.

The main loop runs exactly k times. At each iteration, the algorithm compares the closest available predecessor and successor values. The closer one is appended to the answer and its iterator advances.

Because the stacks always represent the next available candidates in sorted order, the algorithm remains correct throughout execution.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

func closestKValues(root *TreeNode, target float64, k int) []int {

    predecessors := []*TreeNode{}
    successors := []*TreeNode{}

    initPredecessors := func(node *TreeNode) {
        for node != nil {
            if float64(node.Val) < target {
                predecessors = append(predecessors, node)
                node = node.Right
            } else {
                node = node.Left
            }
        }
    }

    initSuccessors := func(node *TreeNode) {
        for node != nil {
            if float64(node.Val) >= target {
                successors = append(successors, node)
                node = node.Left
            } else {
                node = node.Right
            }
        }
    }

    var getPredecessor func() int
    getPredecessor = func() int {

        n := len(predecessors)
        node := predecessors[n-1]
        predecessors = predecessors[:n-1]

        value := node.Val
        node = node.Left

        for node != nil {
            predecessors = append(predecessors, node)
            node = node.Right
        }

        return value
    }

    var getSuccessor func() int
    getSuccessor = func() int {

        n := len(successors)
        node := successors[n-1]
        successors = successors[:n-1]

        value := node.Val
        node = node.Right

        for node != nil {
            successors = append(successors, node)
            node = node.Left
        }

        return value
    }

    initPredecessors(root)
    initSuccessors(root)

    result := []int{}

    for i := 0; i < k; i++ {

        if len(predecessors) == 0 {
            result = append(result, getSuccessor())

        } else if len(successors) == 0 {
            result = append(result, getPredecessor())

        } else {

            predDiff := math.Abs(float64(predecessors[len(predecessors)-1].Val) - target)
            succDiff := math.Abs(float64(successors[len(successors)-1].Val) - target)

            if predDiff <= succDiff {
                result = append(result, getPredecessor())
            } else {
                result = append(result, getSuccessor())
            }
        }
    }

    return result
}

The Go implementation follows the same logic as the Python solution, but several language-specific details differ.

Go does not support nested named functions with automatic closures as conveniently as Python, so helper functions are declared as function variables.

Stacks are implemented using slices. Appending uses append(), and popping removes the last element using slice truncation.

Go also requires explicit conversion from int to float64 before distance calculations.

Nil tree handling is naturally supported because traversal loops terminate when a pointer becomes nil.

Worked Examples

Example 1

Input:

root = [4,2,5,1,3]
target = 3.714286
k = 2

BST structure:

        4
       / \
      2   5
     / \
    1   3

Initialization Phase

Predecessor Stack

Node Action Stack
4 4 >= target, go left []
2 2 < target, push and go right [2]
3 3 < target, push and go right [2, 3]

Successor Stack

Node Action Stack
4 4 >= target, push and go left [4]
2 2 < target, go right [4]
3 3 < target, go right [4]

Now:

predecessors = [2, 3]
successors = [4]

Iteration 1

Compare:

|3 - 3.714286| = 0.714286
|4 - 3.714286| = 0.285714

Choose successor 4.

Result:

[4]

Advance successor iterator.

Next successor becomes 5.

Iteration 2

Compare:

|3 - 3.714286| = 0.714286
|5 - 3.714286| = 1.285714

Choose predecessor 3.

Result:

[4, 3]

Return:

[4, 3]

Example 2

Input:

root = [1]
target = 0
k = 1

Initialization

Predecessor Stack

No values smaller than target.

[]

Successor Stack

[1]

Iteration 1

Predecessor stack is empty, so choose successor.

Result:

[1]

Return:

[1]

Complexity Analysis

Measure Complexity Explanation
Time O(log n + k) average, O(n) worst Stack initialization follows BST height, each extraction processes one node
Space O(log n) average, O(n) worst Stacks store root-to-leaf traversal paths

In a balanced BST, the height is O(log n), so initialization is efficient. Each predecessor or successor extraction visits nodes only once across the entire algorithm.

In the worst case of a completely skewed BST, the height becomes O(n), which increases both time and space complexity accordingly.

Test Cases

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

s = Solution()

# Example 1
root1 = TreeNode(4)
root1.left = TreeNode(2)
root1.right = TreeNode(5)
root1.left.left = TreeNode(1)
root1.left.right = TreeNode(3)

assert sorted(s.closestKValues(root1, 3.714286, 2)) == [3, 4]  # standard example

# Example 2
root2 = TreeNode(1)

assert s.closestKValues(root2, 0.0, 1) == [1]  # single-node tree

# Target exactly matches node
root3 = TreeNode(5)
root3.left = TreeNode(3)
root3.right = TreeNode(7)

assert sorted(s.closestKValues(root3, 5.0, 2)) == [3, 5]  # exact target match

# k equals total nodes
root4 = TreeNode(2)
root4.left = TreeNode(1)
root4.right = TreeNode(3)

assert sorted(s.closestKValues(root4, 2.0, 3)) == [1, 2, 3]  # return all nodes

# Target smaller than all values
root5 = TreeNode(10)
root5.left = TreeNode(5)
root5.right = TreeNode(15)

assert sorted(s.closestKValues(root5, -100.0, 2)) == [5, 10]  # extreme small target

# Target larger than all values
root6 = TreeNode(10)
root6.left = TreeNode(5)
root6.right = TreeNode(15)

assert sorted(s.closestKValues(root6, 100.0, 2)) == [10, 15]  # extreme large target

# Left-skewed tree
root7 = TreeNode(5)
root7.left = TreeNode(4)
root7.left.left = TreeNode(3)
root7.left.left.left = TreeNode(2)

assert sorted(s.closestKValues(root7, 3.5, 2)) == [3, 4]  # skewed BST

# Right-skewed tree
root8 = TreeNode(1)
root8.right = TreeNode(2)
root8.right.right = TreeNode(3)
root8.right.right.right = TreeNode(4)

assert sorted(s.closestKValues(root8, 2.8, 2)) == [2, 3]  # opposite skew

# Floating-point target between nodes
root9 = TreeNode(8)
root9.left = TreeNode(4)
root9.right = TreeNode(12)
root9.left.left = TreeNode(2)
root9.left.right = TreeNode(6)

assert sorted(s.closestKValues(root9, 5.1, 3)) == [4, 6, 8]  # decimal target

Test Case Summary

Test Why
Standard balanced BST Verifies normal behavior
Single-node tree Smallest valid input
Exact target match Ensures equality handled correctly
k equals n Ensures all nodes can be returned
Target below minimum Tests empty predecessor stack
Target above maximum Tests empty successor stack
Left-skewed BST Worst-case height scenario
Right-skewed BST Opposite skew structure
Decimal target Verifies floating-point distance handling

Edge Cases

Target Smaller Than Every Node

If the target is smaller than all BST values, the predecessor stack becomes empty during initialization. A buggy implementation may attempt to access the top of an empty stack.

This solution explicitly checks whether one stack is empty before comparing distances. If predecessors are unavailable, values are taken only from successors.

Target Larger Than Every Node

This is the symmetric opposite case. Here, the successor stack becomes empty because no node value is greater than or equal to the target.

The implementation safely falls back to extracting only predecessors until k values are collected.

Highly Unbalanced BST

A skewed BST behaves almost like a linked list. Recursive solutions can risk excessive recursion depth or lose expected logarithmic performance.

This implementation uses iterative stack traversal instead of recursion, avoiding recursion depth issues entirely. Although worst-case complexity becomes O(n), correctness remains intact.

k Equals Total Number of Nodes

Some implementations accidentally stop early or fail after one iterator becomes empty.

This algorithm continues pulling values from whichever iterator still has remaining nodes, ensuring all n values are eventually returned correctly.