Validate Binary Search Tree
mediumSave
Binary Search TreeDepth-First SearchRecursionTree
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1
Input
[ "{\"val\": 2, \"left\": {\"val\": 1, \"left\": null, \"right\": null}, \"right\": {\"val\": 3, \"left\": null, \"right\": null}}" ]
Output
true
Explanation. The binary tree is a valid binary search tree with the root at 2, a left child at 1, and a right child at 3. All nodes follow the BST property.
Example 2
Input
[ "{\"val\": 5, \"left\": {\"val\": 1, \"left\": null, \"right\": null}, \"right\": {\"val\": 4, \"left\": {\"val\": 3, \"left\": null, \"right\": null}, \"right\": {\"val\": 6, \"left\": null, \"right\": null}}}" ]
Output
false
Explanation. The binary tree violates the BST rules; Node 4 has a left child 3 which is fine but also a right child 6 which should not be under node 4.
Follow-up: How would you handle a situation where the binary tree values include non-integer values, such as strings or floating-point numbers?
Constraints:
The number of nodes in the tree is in the range [1, 10^4]. Integer values could vary from -2^31 to 2^31 - 1. Assume that the tree does not contain duplicate values.
- Views
- 4