Closest Binary Search Tree Value

mediumSave

Binary SearchBinary Search TreeTree

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:

Example 1

Input

{
  "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
}

Output

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.

Example 2

Input

{
  "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
}

Output

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.

Constraints:

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: 1