Balanced Binary Search Tree Check
Medium
Given the root of a binary search tree (BST), determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than one.
Example 1
Input
[ { "val": 3, "left": { "val": 9, "left": null, "right": null }, "right": { "val": 20, "left": { "val": 15, "left": null, "right": null }, "right": { "val": 7, "left": null, "right": null } } } ]
Output
true
Explanation. The given tree [3, 9, 20, null, null, 15, 7] is height-balanced.
Example 2
Input
[ { "val": 1, "left": { "val": 2, "left": { "val": 3, "left": { "val": 4, "left": null, "right": null }, "right": null }, "right": null }, "right": null } ]
Output
false
Explanation. The given tree [1, 2, null, 3, null, null, null, 4] is not height-balanced.
Follow-up: Could you solve the problem in O(n) time complexity where n is the number of nodes in the BST?
Constraints:
The number of nodes in the tree will be in the range [0, 5000].\nNode values will be integers.
- Views
- 13