272. Closest Binary Search Tree Value II

HardStackTreeDepth-First SearchBinary Search TreeTwo PointersBinary TreeHeap (Priority Queue)

Problem Description

The problem provides us with a binary search tree (BST) and a target value target. Our goal is to find k values in the BST that are closest to the target value. The values can be returned in any order. The problem guarantees that there is a unique set of k values in the tree that are closest to the target.

Flowchart Walkthrough

Let's analyze Leetcode 272. Closest Binary Search Tree Value II using the Flowchart. Here’s how we progress through the decision tree:

Is it a graph?

Yes: The binary search tree can be treated like a graph where each node points to its children nodes.

Is it a tree?

Yes: A binary search tree is a specific type of tree.

Since we have established that we are dealing with a tree, we are directed straight to utilize Depth-First Search (DFS).

Conclusion: The flowchart indicates using Depth-First Search for this scenario as it allows us to explore the BST in its entirety to make close value comparisons efficiently.

Intuition

To resolve this problem, we use an in-order traversal of the BST. The reason for this choice is that an in-order traversal of a BST yields the values in sorted order. As we traverse the tree, we compare the values of the nodes with the target value to determine how close they are to the target.

We use a deque (double-ended queue) to keep track of the closest values found so far. The deque maintains the k closest values in sorted order due to the nature of in-order traversal. Here's a step-by-step outline of the intuition:

Perform an in-order traversal (left-root-right) because the BST's property guarantees sorted values.
Use a deque of size k to maintain the closest values to the target. We start by adding values to the deque until it is full.
Once the deque has k elements, we compare the current value (as we continue in-order traversal) with the first element in the deque (the element that is the farthest from the target among those in the deque). If the current value is closer, we remove the first element and add the current value to the deque.
If we find a value that is not closer than the first element in the deque, we can stop the traversal. Since the values are sorted, all subsequent values will be even farther from the target.
After completing the traversal, we return the contents of the deque as our result.

This approach efficiently finds the k closest values by leveraging the sorted nature of the BST and by keeping our list of candidates to a fixed size (k).

Learn more about Stack, Tree, Depth-First Search, Binary Search Tree, Two Pointers, Binary Tree and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a Depth-First Search (DFS) in-order traversal strategy to explore the BST and a deque data structure to keep track of the k closest values. Let's look at how the provided code implements this:

A helper function dfs(root) is defined for traversal purposes. It's a recursive function that takes the current node as its argument and explores it in an in-order fashion (left-root-right).
When the dfs function is called with the BST root, it first checks if the current node is None, meaning it's reached the end of a path in the tree, and in that case, it returns without doing anything further.
The function then proceeds to recursively call itself to explore the left subtree: dfs(root.left).
After exploring the left sub-tree, the function checks if the deque named q is already full (i.e., if it already contains k elements):
- If q is not full, it appends the current node's value to q.
- If q is full, the function compares the absolute difference between the target and the current value (abs(root.val - target)) with the absolute difference between the target and the value at the front of the deque (abs(q[0] - target)):
  - If the current value is closer to the target than the value at the front of q, we popleft from q to remove the farthest value, and append the current value (q.append(root.val)).
  - If the current value is not closer, the traversal is halted as further right nodes will be even farther from the target.
The DFS continues to the right subtree: dfs(root.right), as long as the closest k values are not yet finalized (meaning it returns early if a value is farther from the target than the first value in q).
A deque object q is created outside of the dfs function and is passed by reference into it. A deque is used because it allows efficient addition and removal of elements from the start of the queue (popleft), which is required when we find a closer value and we need to remove the least close value in it.
After the DFS traversal is complete, the function closestKValues returns the current content of the deque q converted to a list with list(q), which contains the k values closest to the target.

By utilizing a modified in-order traversal that stops early when appropriate, and a deque to keep a running set of the closest values, the solution efficiently finds the k values in the BST that are closest to the target value.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the solution approach outlined above to demonstrate how we can find the k values closest to a target within a Binary Search Tree (BST):

Example BST

Consider the following BST, where k = 3 and target = 5:

Our goal is to find the 3 values closest to 5.

Step-by-Step Traversal and Deque Operations

Begin with an empty deque q and start the in-order DFS traversal from the root (4).
Visit the left child, 2.
- Call dfs(2), visit left child (1), and call dfs(1). Since 1 has no left child, append 1 to the deque.
  - q = [1]
- Return to 2, visit right child (3), and call dfs(3). Since 3 has no children, append 3 to deque.
  - q = [1, 3]
- With q still not full, append 2’s value to q.
  - q = [1, 3, 2]
Return to the root, 4. Now q is full.
- Compare 4 with the front of q (1). Since abs(4 - 5) < abs(1 - 5), pop from the left and append 4.
  - q = [3, 2, 4]
Visit the right child, 6.
- Call dfs(6), and compare 6 with the front of q (3).
  - Since abs(6 - 5) < abs(3 - 5), we remove the front value and add 6.
    - q = [2, 4, 6]
  - Visit the right child of 6, which is 7, and compare with the front of q (2).
  - Since abs(7 - 5) > abs(2 - 5), we do not need to visit any more nodes because all subsequent nodes will be farther away.
Conversion to a list and return:
- Convert the deque to a list, resulting in the k values closest to the target: [2, 4, 6]

By following this walkthrough, we have efficiently located the k closest values to the target in the BST.

Solution Implementation

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
12        # Perform in-order depth-first search to traverse the tree.
13        def in_order_dfs(node):
14            if node is None:
15                return
16          
17            # Recurse on the left child.
18            in_order_dfs(node.left)
19          
20            # Process the current node.
21            # If we have fewer than k values, add current node's value.
22            if len(closest_values) < k:
23                closest_values.append(node.val)
24            else:
25                # Once we have k values, check if current node is closer to target
26                # than the first value in the deque. If not, no need to proceed further.
27                if abs(node.val - target) >= abs(closest_values[0] - target):
28                    return
29              
30                # If the current node is closer, pop the first value and append the current value.
31                closest_values.popleft()
32                closest_values.append(node.val)
33          
34            # Recurse on the right child.
35            in_order_dfs(node.right)
36
37        # This deque will store the closest k values encountered so far.
38        closest_values = deque()
39      
40        # Start the in-order traversal of the tree.
41        in_order_dfs(root)
42      
43        # Return the k closest values as a list.
44        return list(closest_values)
45

1class Solution {
2    // Define a list to hold the closest k values.
3    private List<Integer> closestValues;
4  
5    // Define a variable to hold the target value for comparison.
6    private double targetValue;
7  
8    // Define a variable to hold the number of closest values required.
9    private int numOfClosestValues;
10  
11    // Public method to call to find the k closest values to a target in a binary search tree.
12    public List<Integer> closestKValues(TreeNode root, double target, int k) {
13        closestValues = new LinkedList<>();
14        targetValue = target;
15        numOfClosestValues = k;
16        inOrderTraversal(root);
17        return closestValues;
18    }
19  
20    // Helper method to perform in-order traversal of the binary tree.
21    private void inOrderTraversal(TreeNode node) {
22        // Base case: if the node is null, return immediately.
23        if (node == null) {
24            return;
25        }
26      
27        // Recursive call on the left subtree.
28        inOrderTraversal(node.left);
29      
30        // If the current size of the closestValues list is less than k,
31        // add the current node's value to the list.
32        if (closestValues.size() < numOfClosestValues) {
33            closestValues.add(node.val);
34        } else {
35            // If adding the current node's value to the list does not bring it closer to the target,
36            // stop the traversal since nodes farther to the right will be even less close.
37            if (Math.abs(node.val - targetValue) >= Math.abs(closestValues.get(0) - targetValue)) {
38                return;
39            }
40          
41            // Remove the first/oldest element in the list
42            closestValues.remove(0);
43          
44            // Add the current node's value to the list
45            closestValues.add(node.val);
46        }
47      
48        // Recursive call on the right subtree.
49        inOrderTraversal(node.right);
50    }
51}
52

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12
13class Solution {
14public:
15    std::queue<int> closeValuesQueue; // Queue to keep track of the k closest values
16    double targetValue;               // Target value to compare against
17    int kValues;                      // Number of closest values to find
18  
19    // Function to find k values in the BST closest to the target value
20    std::vector<int> closestKValues(TreeNode* root, double target, int k) {
21        this->targetValue = target;
22        this->kValues = k;
23        traverseInOrder(root);
24      
25        // Extract values from queue and store them in an answer vector
26        std::vector<int> closestValues;
27        while (!closeValuesQueue.empty()) {
28            closestValues.push_back(closeValuesQueue.front());
29            closeValuesQueue.pop();
30        }
31        return closestValues;
32    }
33  
34    // In-order traversal of the BST
35    void traverseInOrder(TreeNode* node) {
36        if (!node) return; // Base case: node is null
37      
38        // Traverse left subtree
39        traverseInOrder(node->left);
40      
41        // Check if the number of elements in the queue is less than k
42        if (closeValuesQueue.size() < kValues)
43            closeValuesQueue.push(node->val);
44        else {
45            // Check if the current value is closer to the target than the front of the queue
46            if (std::abs(node->val - targetValue) >= std::abs(closeValuesQueue.front() - targetValue))
47                return; // If not, we don't need to continue as the right subtree will have even larger values
48            closeValuesQueue.pop(); // Remove the furthest value
49            closeValuesQueue.push(node->val); // Add the current, closer value
50        }
51      
52        // Traverse right subtree
53        traverseInOrder(node->right);
54    }
55};
56

1// Tree node structure
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8let closeValuesQueue: number[] = []; // Queue to keep track of the k closest values
9let targetValue: number = 0;         // Target value to compare against
10let kValues: number = 0;             // Number of closest values to find
11
12// Function to find k values in the BST closest to the target value
13function closestKValues(root: TreeNode | null, target: number, k: number): number[] {
14    targetValue = target;
15    kValues = k;
16    closeValuesQueue = []; // initialize the queue to be empty
17    traverseInOrder(root);
18
19    // The queue is already a list of closest values when using TypeScript arrays
20    return closeValuesQueue;
21}
22
23// In-order traversal of the BST
24function traverseInOrder(node: TreeNode | null): void {
25    if (!node) return; // Base case: node is null
26
27    // Traverse left subtree
28    traverseInOrder(node.left);
29
30    // Check if the number of elements in the queue is less than k
31    if (closeValuesQueue.length < kValues) {
32        closeValuesQueue.push(node.val);
33    } else {
34        // Check if the current value is closer to the target than the first element of the queue
35        if (Math.abs(node.val - targetValue) < Math.abs(closeValuesQueue[0] - targetValue)) {
36            closeValuesQueue.shift(); // Remove the furthest value
37            closeValuesQueue.push(node.val); // Add the current, closer value
38        } else {
39            // If not closer, we can break here because the right subtree will not have closer values
40            return;
41        }
42    }
43
44    // After processing current node, ensure queue is sorted by closest to the target value
45    closeValuesQueue.sort((a, b) => Math.abs(a - targetValue) - Math.abs(b - targetValue));
46
47    // Traverse right subtree
48    traverseInOrder(node.right);
49}
50

Time and Space Complexity

The time complexity of the provided code is O(N) where N denotes the number of nodes in the binary tree. This is because the dfs function performs an in-order traversal of the entire tree, visiting each node exactly once.

The space complexity is O(H + k) where H denotes the height of the binary tree, which is the space required for the call stack during the recursive traversal, and k is the space for storing closest values in the queue. In the worst case, the height of the tree can be O(N) when the tree is skewed, leading to the worst-case space complexity of O(N + k). In a balanced tree, however, the height H is O(log N), leading to a more typical space complexity of O(log N + k).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know