closest_binary_search_tree_value

View Source

 1from collections import deque
 2from typing import Optional
 3from utils import TreeNode, to_binary_tree
 4# @leet start
 5class Solution:
 6    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
 7        """
 8        This problem is about finding the closest tree node value to a target.
 9        To find the closest value, we want to minimize abs(node.val - target) for
10        each node in the tree.
11
12        Naively this is pretty easy -- we iterate through all the nodes in the tree
13        and then calculate abs(node.val - target) and return the closest node.
14        This takes $O(n)$ time.
15
16        If this was a binary tree, this would be the best we could do -- we must
17        traverse all the nodes in a binary tree to find the closest value, because
18        we have no way to prune any of the nodes during our search, since there is
19        no ordering.
20
21        However, since this is a Binary Search Tree, with a given ordering, we can
22        reduce our time spent to $O(log_2(n))$, if the tree is balanced.
23
24        To do this, we have to prune one side of the tree as we go down in, thus
25        only looking at $log_2(n)$ nodes.
26
27        There are three possible cases:
28        1. node.val == target.
29        In this case, we can just return this value, since the target is in the tree.
30        2. node.val > target.
31        We can check to see if we have the closest value. As well, we only want to check
32        values on the left, since they could possibly be closer to the target.
33        Any values on the right will only be greater, and thus, further from the target.
34        3. node.val < target.
35        We can check to see if we have the closest value. As well, we only want to check
36        values on the right, since they could possibly be closer to the target.
37        Any values on the left will only be lesser, and thus, further from the target.
38
39        So, we code that up and return the closest node.
40        """
41        q = deque()
42        if not root:
43            raise RuntimeError('Root must not be None')
44        q.append(root)
45        min_dist = abs(root.val - target)
46        min_val = root.val
47        while q:
48            node = q.popleft()
49            if abs(node.val - target) < min_dist:
50                min_dist = abs(node.val - target)
51                min_val = node.val
52            if abs(node.val - target) == min_dist:
53                min_val = min(min_val, node.val)
54            if node.right and node.val < target:
55                q.append(node.right)
56            if node.left and node.val > target:
57                q.append(node.left)
58        return min_val
59
60# @leet end
61sol = Solution()
62def test():
63    assert(sol.closestValue(to_binary_tree([4,2,5,1,3]), 3.714) == 4)
64    assert(sol.closestValue(to_binary_tree([1]), 4.23) == 1)

class Solution: View Source

 6class Solution:
 7    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
 8        """
 9        This problem is about finding the closest tree node value to a target.
10        To find the closest value, we want to minimize abs(node.val - target) for
11        each node in the tree.
12
13        Naively this is pretty easy -- we iterate through all the nodes in the tree
14        and then calculate abs(node.val - target) and return the closest node.
15        This takes $O(n)$ time.
16
17        If this was a binary tree, this would be the best we could do -- we must
18        traverse all the nodes in a binary tree to find the closest value, because
19        we have no way to prune any of the nodes during our search, since there is
20        no ordering.
21
22        However, since this is a Binary Search Tree, with a given ordering, we can
23        reduce our time spent to $O(log_2(n))$, if the tree is balanced.
24
25        To do this, we have to prune one side of the tree as we go down in, thus
26        only looking at $log_2(n)$ nodes.
27
28        There are three possible cases:
29        1. node.val == target.
30        In this case, we can just return this value, since the target is in the tree.
31        2. node.val > target.
32        We can check to see if we have the closest value. As well, we only want to check
33        values on the left, since they could possibly be closer to the target.
34        Any values on the right will only be greater, and thus, further from the target.
35        3. node.val < target.
36        We can check to see if we have the closest value. As well, we only want to check
37        values on the right, since they could possibly be closer to the target.
38        Any values on the left will only be lesser, and thus, further from the target.
39
40        So, we code that up and return the closest node.
41        """
42        q = deque()
43        if not root:
44            raise RuntimeError('Root must not be None')
45        q.append(root)
46        min_dist = abs(root.val - target)
47        min_val = root.val
48        while q:
49            node = q.popleft()
50            if abs(node.val - target) < min_dist:
51                min_dist = abs(node.val - target)
52                min_val = node.val
53            if abs(node.val - target) == min_dist:
54                min_val = min(min_val, node.val)
55            if node.right and node.val < target:
56                q.append(node.right)
57            if node.left and node.val > target:
58                q.append(node.left)
59        return min_val

def closestValue(self, root: Optional[utils.TreeNode], target: float) -> int: View Source

 7    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
 8        """
 9        This problem is about finding the closest tree node value to a target.
10        To find the closest value, we want to minimize abs(node.val - target) for
11        each node in the tree.
12
13        Naively this is pretty easy -- we iterate through all the nodes in the tree
14        and then calculate abs(node.val - target) and return the closest node.
15        This takes $O(n)$ time.
16
17        If this was a binary tree, this would be the best we could do -- we must
18        traverse all the nodes in a binary tree to find the closest value, because
19        we have no way to prune any of the nodes during our search, since there is
20        no ordering.
21
22        However, since this is a Binary Search Tree, with a given ordering, we can
23        reduce our time spent to $O(log_2(n))$, if the tree is balanced.
24
25        To do this, we have to prune one side of the tree as we go down in, thus
26        only looking at $log_2(n)$ nodes.
27
28        There are three possible cases:
29        1. node.val == target.
30        In this case, we can just return this value, since the target is in the tree.
31        2. node.val > target.
32        We can check to see if we have the closest value. As well, we only want to check
33        values on the left, since they could possibly be closer to the target.
34        Any values on the right will only be greater, and thus, further from the target.
35        3. node.val < target.
36        We can check to see if we have the closest value. As well, we only want to check
37        values on the right, since they could possibly be closer to the target.
38        Any values on the left will only be lesser, and thus, further from the target.
39
40        So, we code that up and return the closest node.
41        """
42        q = deque()
43        if not root:
44            raise RuntimeError('Root must not be None')
45        q.append(root)
46        min_dist = abs(root.val - target)
47        min_val = root.val
48        while q:
49            node = q.popleft()
50            if abs(node.val - target) < min_dist:
51                min_dist = abs(node.val - target)
52                min_val = node.val
53            if abs(node.val - target) == min_dist:
54                min_val = min(min_val, node.val)
55            if node.right and node.val < target:
56                q.append(node.right)
57            if node.left and node.val > target:
58                q.append(node.left)
59        return min_val

This problem is about finding the closest tree node value to a target. To find the closest value, we want to minimize abs(node.val - target) for each node in the tree.

Naively this is pretty easy -- we iterate through all the nodes in the tree and then calculate abs(node.val - target) and return the closest node. This takes $O(n)$ time.

If this was a binary tree, this would be the best we could do -- we must traverse all the nodes in a binary tree to find the closest value, because we have no way to prune any of the nodes during our search, since there is no ordering.

However, since this is a Binary Search Tree, with a given ordering, we can reduce our time spent to $O(log_2(n))$, if the tree is balanced.

To do this, we have to prune one side of the tree as we go down in, thus only looking at $log_2(n)$ nodes.

There are three possible cases:

node.val == target. In this case, we can just return this value, since the target is in the tree.
node.val > target. We can check to see if we have the closest value. As well, we only want to check values on the left, since they could possibly be closer to the target. Any values on the right will only be greater, and thus, further from the target.
node.val < target. We can check to see if we have the closest value. As well, we only want to check values on the right, since they could possibly be closer to the target. Any values on the left will only be lesser, and thus, further from the target.

So, we code that up and return the closest node.

sol = <Solution object>

def test(): View Source

63def test():
64    assert(sol.closestValue(to_binary_tree([4,2,5,1,3]), 3.714) == 4)
65    assert(sol.closestValue(to_binary_tree([1]), 4.23) == 1)