Balanced Binary Subtree
Medium
Given a binary tree, 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
[ { "value": 1, "left": { "value": 2, "left": null, "right": null }, "right": { "value": 3, "left": null, "right": null } } ]
Output
true
Explanation. The tree has only three nodes and is automatically height-balanced.
Example 2
Input
[ { "value": 1, "left": { "value": 2, "left": { "value": 4, "left": null, "right": null }, "right": null }, "right": { "value": 3, "left": null, "right": null } } ]
Output
true
Explanation. The tree is height-balanced, as the depth difference between the left and right subtree for every node is no more than 1.
Example 3
Input
[ { "value": 1, "left": { "value": 2, "left": { "value": 3, "left": { "value": 4, "left": null, "right": null }, "right": null }, "right": null }, "right": null } ]
Output
false
Explanation. The tree is not height-balanced because the node with value 2 has a left subtree with a height of 3 and no right subtree.
Follow-up: Can you improve your solution to be more efficient than O(n log n)?
Constraints:
The binary tree may have up to 5000 nodes.
- Views
- 9