Balanced Binary Tree
A binary tree is considered balanced if, for every node in the tree, the difference in the height of its left and right subtrees is at most 1.
In other words, the height of the two subtrees for every node in the tree differs by no more than one.
The height of a subtree is the number of edges on the longest path from that subtree's root down to any leaf node. (This is distinct from depth, which measures the distance from the tree's root down to a specific node.)
Note: An empty tree is considered balanced by definition.
In that case, given a binary tree, determine if it is balanced.
Parameter
tree: A binary tree.
Result
- A boolean representing whether the tree given is balanced.
Examples
Example 1
Input:
Output: true
Explanation: By definition, this is a balanced binary tree.
Example 2
Input:
Output: false
Explanation: The subtrees of the node labelled 3 has a height difference of 3 (right subtree has height 2 and left
subtree is empty with height -1), so
it is not balanced.