We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Binary Search Tree Value II

Number: 272

Difficulty: Hard

Paid? Yes

Companies: LinkedIn, Meta, Google

Problem Description

Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. The answer can be returned in any order and it is guaranteed that there is only one unique set of k values closest to the target.

Key Insights

  • The BST property allows efficient narrowing down of candidate nodes.
  • Using two stacks to track predecessors (values <= target) and successors (values > target) can efficiently yield the closest values.
  • A modified in-order traversal helps in retrieving the next closest candidate from either side.
  • Merging two sorted lists of candidate values based on absolute difference with the target is the key step.

Space and Time Complexity

Time Complexity: O(k + log n) – O(log n) to initialize the two stacks and O(k) to collect k elements. Space Complexity: O(log n) – due to the stack space in a balanced BST.

Solution

We can solve the problem by splitting it into two parts:

  1. Build two stacks:

    • The predecessor stack for nodes with values less than or equal to target.
    • The successor stack for nodes with values greater than target.

    To build these stacks, traverse the BST starting from the root and push nodes along the path: if the node's value is less than or equal to target, push it to the predecessor stack and go right; if greater, push it to the successor stack and go left.

  2. Merge the two stacks:

    • At each step, compare the top element of the predecessor stack (if available) and the successor stack (if available) based on their distance from the target.
    • Pop from the stack with the closer candidate and add that value to the result list.
    • For the popped node, update the given stack by moving to the next appropriate node in the in-order traversal (for predecessor, go to left child then rightmost descendant; for successor, go to right child then leftmost descendant).
    • Repeat until k values have been collected.

Key Data Structures and Techniques:

  • Two stacks to simulate reverse and forward in-order traversals.
  • Merge technique to choose the closest candidate at each iteration.

Code Solutions

# Python solution for Closest Binary Search Tree Value II

# 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

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int):
        # Helper function to initialize predecessors stack
        def initPredecessor(node):
            while node:
                # If node value is less or equal, push to preds and go right
                if node.val <= target:
                    preds.append(node)
                    node = node.right
                else:
                    node = node.left

        # Helper function to initialize successors stack
        def initSuccessor(node):
            while node:
                # If node value is greater than target, push to succs and go left
                if node.val > target:
                    succs.append(node)
                    node = node.left
                else:
                    node = node.right

        # Helper function to get next predecessor value
        def getPredecessor():
            if not preds: return None
            node = preds.pop()
            val = node.val
            # Traverse the left subtree: push nodes from left child then rightmost branch
            node = node.left
            while node:
                preds.append(node)
                node = node.right
            return val

        # Helper function to get next successor value
        def getSuccessor():
            if not succs: return None
            node = succs.pop()
            val = node.val
            # Traverse the right subtree: push nodes from right child then leftmost branch
            node = node.right
            while node:
                succs.append(node)
                node = node.left
            return val

        preds, succs = [], []
        # Initialize the stacks with correct boundary values
        initPredecessor(root)
        initSuccessor(root)
        
        result = []
        # If the closest value from predecessor and successor are same, skip one to avoid duplicates.
        if preds and succs and preds[-1].val == succs[-1].val:
            getPredecessor()

        # Merge k closest values
        for _ in range(k):
            if not preds:
                # Only successors left
                result.append(getSuccessor())
            elif not succs:
                # Only predecessors left
                result.append(getPredecessor())
            else:
                # Compare which candidate is closer to the target
                if abs(preds[-1].val - target) <= abs(succs[-1].val - target):
                    result.append(getPredecessor())
                else:
                    result.append(getSuccessor())
        return result
← Back to All Questions