Closest Binary Search Tree Value
Given the root of a Binary Search Tree (BST) and a target number target, return the value in the BST that is closest to the target. Assume that there can only be one closest value.
Function Signature: def closest_value(root: TreeNode, target: float) -> int:
{ "tree": { "val": 4, "left": { "val": 2, "left": { "val": 1, "left": null, "right": null }, "right": { "val": 3, "left": null, "right": null } }, "right": { "val": 5, "left": null, "right": null } }, "target": 3.714 }
Explanation. The nodes of the tree are 1, 2, 3, 4, and 5. The values 3 and 4 are closest to 3.714, with 4 being the closest.
{ "tree": { "val": 9, "left": { "val": 4, "left": { "val": 2, "left": null, "right": null }, "right": { "val": 6, "left": null, "right": { "val": 7, "left": null, "right": null } } }, "right": { "val": 12, "left": null, "right": { "val": 15, "left": null, "right": null } } }, "target": 5 }
Explanation. The closest value to the target 5 in this tree are 4 and 6, but 4 is closer.
Follow-up: Discuss the implementation details for the closest value search in terms of time complexity and why the properties of BST assist in this problem.
The number of nodes in the tree will be in the range `[1, 10^4]`. Values of nodes are unique and lie within the range `[-10^9, 10^9]`. The target value is a floating number.
- Views
- 11