270. Closest Binary Search Tree Value

EasyTreeDepth-First SearchBinary Search TreeBinary SearchBinary Tree

Problem Description

In this problem, you're given the root of a binary search tree (BST) and a target value. You need to find the value in the BST that is closest to the target value. It's important to understand that a BST is a special type of binary tree where for each node, the left child has a value less than the node's value, and the right child has a value greater than the node's value. This property of BSTs allows efficient searching, similar to binary search in a sorted array.

When looking for the value closest to the target, if there are multiple such values that are equally close, you should return the smaller one. Your task is to implement an algorithm that will traverse the BST and return the value that meets these conditions.

Flowchart Walkthrough

To analyze the problem in Leetcode 270, Closest Binary Search Tree Value, let's use the flowchart to deduce the appropriate algorithm. Here's the step-by-step examination:

Is it a graph?

Yes: In this case, the binary search tree (BST) can be thought of as a graph where each node is a vertex and edges exist between parent and child nodes.

Is it a tree?

Yes: A binary search tree is a specialized type of tree that follows specific ordering properties.

DFS

Considering we have a tree structure and are focusing on finding a specific value (or the closest value) within the tree, one appropriate approach to traverse or search through a tree structure is using Depth-First Search (DFS). This method allows exploring as far as possible down each branch before backtracking, which is suitable here as we need to examine values to find the closest to the target.

Conclusion: The flowchart suggests using DFS for this tree structure problem to efficiently locate the closest value in a binary search tree to a given target value. DFS is a fitting choice for navigating each node while comparing their values to the target, potentially reducing the search space exponentially by leveraging the ordering properties of the BST.

Intuition

To solve this problem, we can utilize the properties of the BST to guide our search similar to a binary search algorithm. The intuition here is that, when searching in a BST, you can move left or right from a node depending on how the current node's value compares to the target value. If the current node's value is greater than the target, then the closest value can either be the current node's value or in the left subtree. If the current node's value is less than the target, then the closest value can either be the current node's value or in the right subtree.

We use the absolute difference between the current node's value and the target value to judge closeness. As we traverse the BST, we keep updating the closest value found so far. We start with the root node's value as the initial closest value and an infinite difference to ensure any actual number found is nearer.

The key elements for our approach here:

We will traverse the BST in a while loop, choosing left or right child nodes depending on how they compare to the target value.
In each step of the traversal, we will keep track of the closest value and the smallest difference seen so far.
We only update the closest value if the current node offers a closer or equal but smaller value compared to what we have seen so far.
Since we are doing a binary search-like traversal, the time complexity is O(h) where h is the height of the BST. In the worst case, this can be O(n) if the tree is skewed, but it's generally more efficient than a full traversal.

By following this approach, we are able to leverage the BST property to efficiently find the value closest to the given target.

Learn more about Tree, Depth-First Search, Binary Search Tree, Binary Search and Binary Tree patterns.

Solution Approach

The implementation follows a binary search approach which, in the context of BST, translates into a traversal where the decision to move left or right is based on how the current node's value compares to the target value.

Algorithm

Initialize two variables, ans to store the current closest value and mi to store the minimum difference, which is initially set to infinity (inf).
Begin a while loop that continues as long as there is a valid node (while root is not None).
For every node visited, calculate the absolute difference t between the node's value (root.val) and the target.
If this difference is less than the current minimum difference (mi), update mi to this new difference, and set ans to the current node's value (root.val).
If there's a tie in differences (meaning the current difference t is exactly equal to the mi), and the current node's value is smaller than the ans, update ans to the current node's value. This ensures that in case of multiple closest values, the smallest one is chosen.
Decide the direction of traversal:
- If the current node's value is greater than the target, move to the left child (root = root.left), since a smaller value closer to the target might be found there.
- If the current node's value is less than or equal to the target, move to the right child (root = root.right), as a value closer to the target (or a larger value that is equally close) might be found.
Once the while loop exits (because root becomes None), return ans, which will hold the closest value found during the traversal.

Data Structures

The primary data structure we need is the BST, represented by the TreeNode class, which contains val (the value of the node), left (left subtree), and right (right subtree). Variables ans and mi are integers that help us keep track of the closest value and the minimum difference found during the traversal.

Patterns Used

The main pattern used here is Binary Search. In a sorted array, binary search compares the target with the middle element and decides to continue searching in the left or right halve, effectively cutting down the search space by half in each step. Similarly, in a BST, each decision to move left or right at a node reduces the potential search space considering the ordered nature of BST, where left subtree contains values smaller than the node and the right subtree contains values larger than the node.

This implementation allows us to find the closest value to the target with the efficiency of binary search, thus utilizing the BST's ordered structure to its full advantage.

Code Implementation

The solution definition in Python using the described algorithm is as follows:

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        ans, mi = root.val, inf
        while root:
            t = abs(root.val - target)
            if t < mi or (t == mi and root.val < ans):
                mi = t
                ans = root.val
            if root.val > target:
                root = root.left
            else:
                root = root.right
        return ans

In this implementation, Optional[TreeNode] indicates that root may be either an instance of TreeNode or None.

By adhering to this approach, we leverage the given structure of the BST to efficiently locate the closest value to the target. The algorithm is optimized to run with a time complexity that is dependent on the height of the tree.

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 illustrate the solution approach with a small example. Consider the following BST and a target value of 4.5:

We will walk through the algorithm step-by-step with this BST:

Initialize:
- ans = 4 (First node value)
- mi = inf (As we haven't calculated any differences yet)
First iteration (Node = 4):
- Calculate the absolute difference t between root.val (4) and the target (4.5), which is t = 0.5.
- Since t < mi, update mi = 0.5 and ans = 4.
- Node value 4 is less than the target, so move right to find a potentially closer value.
Second iteration (Node = 5):
- New t is 0.5 (5 - 4.5).
- t is equal to the current mi, and since we prefer smaller values, we do not update ans, keeping ans = 4.
- Node value 5 is greater than the target, so move left to find a potentially closer, smaller value.
Third iteration (Node = 2):
- Now, the tree node is None because there is no left child of node 5, so we stop.

As there are no more nodes to visit, we return the ans. In this case, ans = 4, which is the closest value to the target 4.5 in the BST given. If there had been nodes on the left side of the current node 5, the algorithm would have continued evaluating those nodes.

This walkthrough demonstrates how the decision to move left or right at each node effectively narrows the search utilizing the BST property and binary search principle. The algorithm ensures we do not traverse the entire tree but only the path that could potentially contain the closest value. Given its reliance on tree height, it offers a time-efficient solution.

Solution Implementation

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def closest_value(self, root: TreeNode, target: float) -> int:
9        # Initialize the closest_value with the root's value
10        closest_value = root.val
11      
12        # Initialize the minimum difference found
13        minimum_difference = float('inf')
14
15        # Iterate over the nodes of the binary search tree
16        while root:
17            # Calculate the current difference between node's value and the target
18            current_difference = abs(root.val - target)
19
20            # If the current difference is smaller or equal but with a lesser value, update the closest_value
21            if current_difference < minimum_difference or (current_difference == minimum_difference and root.val < closest_value):
22                minimum_difference = current_difference
23                closest_value = root.val
24          
25            # Move left if the target is smaller than the current node's value
26            if root.val > target:
27                root = root.left
28            # Otherwise, move right
29            else:
30                root = root.right
31      
32        # Once we find the closest value, return it
33        return closest_value
34

1class Solution {
2    public int closestValue(TreeNode root, double target) {
3        int closestValue = root.val; // Initialize closest value to root's value
4        double minDifference = Double.MAX_VALUE; // Initialize minimum difference to maximum possible value
5
6        // Traverse the tree starting from the root
7        while (root != null) {
8            // Current difference between node's value and the target value
9            double currentDifference = Math.abs(root.val - target);
10
11            // If current difference is smaller than previous minDifference
12            // or current difference is equal but value is smaller than previously stored value (closer to target)
13            if (currentDifference < minDifference || (currentDifference == minDifference && root.val < closestValue)) {
14                minDifference = currentDifference; // Update the smallest difference
15                closestValue = root.val; // Update the closest value
16            }
17
18            // If the current node's value is greater than the target,
19            // the closer value must be in the left subtree
20            if (root.val > target) {
21                root = root.left;
22            }
23            // Otherwise, it must be in the right subtree
24            else {
25                root = root.right;
26            }
27        }
28        // After traversing the tree, return the value that is closest to the target
29        return closestValue;
30    }
31}
32

1// Define a structure for the Binary Tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor for creating a node without children.
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    // Constructor for creating a leaf node with a specific value.
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    // Constructor for creating a node with a specific value and left and right children.
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14// Solution class contains methods to solve the problem.
15class Solution {
16public:
17    // Method that finds the value in the binary tree which is closest to the target value.
18    int closestValue(TreeNode* root, double target) {
19        // Initialize the closest value reference as the root value.
20        int closestValueRef = root->val;
21        // Initialize minimum difference seen so far to maximum possible integer value.
22        double minimumDiff = INT_MAX;
23
24        // Iterate down the tree until we reach a leaf (NULL) node.
25        while (root) {
26            // Calculate current difference between node value and target.
27            double currentDiff = abs(root->val - target);
28
29            // Check if the current difference is less than the minimum difference found so far.
30            // If the differences are equal, we prioritize smaller values per the problem's constraint.
31            if (currentDiff < minimumDiff || (currentDiff == minimumDiff && root->val < closestValueRef)) {
32                minimumDiff = currentDiff;  // Update the minimum difference.
33                closestValueRef = root->val;  // Update the closest value reference.
34            }
35
36            // Decide to go left or right in the tree depending on the comparison of the current node's value and target.
37            if (root->val > target) {
38                root = root->left;  // Target is smaller, go left.
39            } else {
40                root = root->right;  // Target is larger, go right.
41            }
42        }
43
44        // Return the closest value found.
45        return closestValueRef;
46    }
47};
48

1// Definition for a binary tree node using TypeScript syntax with explicit types.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Finds the value in a binary search tree that is closest to the target value.
10 * @param {TreeNode | null} root - The root of the binary search tree.
11 * @param {number} target - The target value to find the closest node to.
12 * @returns {number} - The value of the closest node.
13 */
14function closestValue(root: TreeNode | null, target: number): number {
15  // Set an initial answer to the root's value if the root exists, otherwise 0.
16  let closestValue: number = root ? root.val : 0;
17  // Initialize a variable to store the smallest difference encountered.
18  let minDifference: number = Number.MAX_VALUE;
19
20  // Traverse the tree starting from the root.
21  while (root) {
22    // Compute the absolute difference between the current node's value and the target.
23    const currentDifference: number = Math.abs(root.val - target);
24    // If the current difference is smaller than any previously encountered,
25    // or if it's the same but the value is less than our current answer, update the answer.
26    if (currentDifference < minDifference || (currentDifference === minDifference && root.val < closestValue)) {
27      minDifference = currentDifference;
28      closestValue = root.val;
29    }
30    // Decide to move left or right in the tree based on how the current node's value compares to the target.
31    if (root.val > target) {
32      root = root.left;  // Move left if the current value is greater than the target.
33    } else {
34      root = root.right; // Move right if the current value is less than or equal to the target.
35    }
36  }
37  // Return the value of the closest node after traversing the tree.
38  return closestValue;
39}
40

Time and Space Complexity

Time Complexity

The time complexity of this function depends on the height of the binary tree. In the worst-case scenario, the tree is skewed (i.e., each node has only one child), resulting in a height of n, where n is the number of nodes in the tree. In that case, we would have to visit every node, making the time complexity O(n).

In the best-case scenario, the binary tree is balanced, and the height of the tree would be log(n). Since in a balanced tree, with each comparison of the node's value to the target, we are effectively eliminating half of the potential nodes in which the closest value could reside, we end up with a time complexity of O(log(n)).

Therefore, the overall time complexity can be expressed as O(h), where h denotes the height of the tree, which is between O(log(n)) and O(n).

Space Complexity

The space complexity of the given function is O(1). This is because the function only uses a constant amount of extra space for a few variables (ans, mi, and t) regardless of the input size. It is an iterative solution that does not incur any additional stack space usage that would be associated with recursion. Therefore, no matter how large the binary tree is, the space used by the function remains the same.

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:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers