270. Closest Binary Search Tree Value

EasyTreeDepth-First SearchBinary Search TreeBinary SearchBinary Tree
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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

  1. Initialize two variables, ans to store the current closest value and mi to store the minimum difference, which is initially set to infinity (inf).
  2. Begin a while loop that continues as long as there is a valid node (while root is not None).
  3. For every node visited, calculate the absolute difference t between the node's value (root.val) and the target.
  4. 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).
  5. 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.
  6. 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.
  7. 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:

1class Solution:
2    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
3        ans, mi = root.val, inf
4        while root:
5            t = abs(root.val - target)
6            if t < mi or (t == mi and root.val < ans):
7                mi = t
8                ans = root.val
9            if root.val > target:
10                root = root.left
11            else:
12                root = root.right
13        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.

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

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following BST and a target value of 4.5:

1        4
2       / \
3     2    5
4   /  \
5  1    3

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

  1. Initialize:

    • ans = 4 (First node value)
    • mi = inf (As we haven't calculated any differences yet)

  2. 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.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Search Tree Intro

Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ