Given a binary search tree and a decimal target, find the value closest to the target. Why can you stop descending one side?
Predict first
What is the closest value for each target?
final class TreeNode {
let val: Int
var left: TreeNode?, right: TreeNode?
init(_ v: Int) { val = v }
}
func insert(_ root: TreeNode?, _ v: Int) -> TreeNode {
guard let root else { return TreeNode(v) }
if v < root.val { root.left = insert(root.left, v) } else { root.right = insert(root.right, v) }
return root
}
func closest(_ root: TreeNode?, to target: Double) -> Int? {
var best: Int? = nil
var node = root
while let n = node {
if best == nil || abs(Double(n.val) - target) < abs(Double(best!) - target) { best = n.val }
node = target < Double(n.val) ? n.left : n.right // the other side cannot be closer
}
return best
}
var root: TreeNode? = nil
for v in [4, 2, 5, 1, 3] { root = insert(root, v) }
print(closest(root, to: 3.714286) ?? -1)
print(closest(root, to: 2.4) ?? -1)
print(closest(root, to: 100) ?? -1)
print(closest(root, to: -5) ?? -1)
print(closest(nil, to: 1.0) as Any)- 4 / 2 / 5 / 1 / nil
- 4 / 3 / 5 / 1 / nil
- 3 / 2 / 5 / 1 / 0
Mental model. Looking for the street number closest to 37 on a street whose numbers rise left to right: at each house you only need to look the way 37 lies, because the other way only gets further.
Use the search property: at each node compare the node’s distance to the target with the best so far, then go left if the target is smaller than the node’s value and right otherwise. The subtree you skip holds only values on the far side of this node from the target, so none of them can be closer than this node is. That makes it O(h) time (the height; O(log n) for a balanced tree, O(n) for a skewed one) and O(1) memory when done with a loop instead of recursion. Compare as Double, since the target is fractional and the node values are integers.
Ask about ties (a target exactly between two values) and say which you return; the strict < keeps the first one met. The check covers the usual targets: 3.714286 gives 4, 2.4 gives 2, and targets beyond either end return the extreme (100 gives 5, -5 gives 1). An empty tree returns nil (use an optional rather than a sentinel such as 0, which could be a real value). The same walk finds the floor and the ceiling, and a variation asks for the k closest, which uses an in-order traversal with a two-pointer or heap. Reported at Uber (anonymous, unverified).
The walk keeps the best candidate and follows the target; outside the range it returns the nearest end and an empty tree gives nil.
Common traps
- Searching both subtrees. That is O(n) and misses the point of the ordering.
- Returning 0 for an empty tree. Zero can be a valid value; use
nil.
They might follow up with
- How would you find the k closest values? In-order traversal keeps a sorted stream; slide a window of size k or use a max-heap.
- What if the tree is not a BST? You must visit every node: O(n).
Related questions
- 29.2.4 Return the values you see when looking at a binary tree from its right side. How does a level-order walk give…
- 29.2.5 Print the boundary of an N-ary tree counterclockwise: root, left edge, leaves left to right, right edge going…
- 29.2.1 Reverse a singly linked list in Swift, iteratively and recursively. What can go wrong with long lists?
← Implement a hash map from scratch (get, set, remove), then extend it… Return the values you see when looking at a binary tree from its… →