A height-balanced binary tree is a binary tree in which the left and right subtrees of every node differ in height by no more than 1
.
This means that if even one node has a height difference of more than 1
for the left and right subtrees, then it is not a balanced binary tree.
To check whether or not the tree above is balanced, we need to check if every node is balanced.
3
The height of the left subtree for node 3
is 1
since it only has one left child,9
, and the height of the right subtree for node 3
is 2
.
We can calculate the height for the right subtree as $20 --- 15$ or $20 --- 7$, as it is the same.
The difference between the left and right subtrees for node 3
is 1
, so this node is balanced.
Now, we need to check the remaining nodes.
9
There is no left subtree or right subtree for node 9
, so the difference between the height of the left and right subtrees for node 9
is 0
. Since 0
is less than 1
, node 9
is balanced.
20
The height of the left subtree is 1
for node 20
since it has only one node, 15
. The height of the right subtree for node 20
is 1
since it has one node, 7
.
Since the difference between the subtrees is 0
, node 20
is balanced.
15
There is no left subtree or right subtree for node 15
, so the difference between the height of the left and right subtrees for node 15
is 0
. Since 0
is less than 1
, node 15
is balanced.
7
There is no left or right subtree for node 7
, so the difference between the height of the left and right subtrees is 0
. Since 0
is less than 1
, node 7
is balanced.
Since every node is balanced in this binary tree, then it is a balanced binary tree
.
To check if the binary tree below is balanced or not, we will start with node 1
.
The height of the left subtree for node 1
is 3
.
The height of the right subtree for node 1
is 1
.
Since the absolute difference between the subtrees is 2
, node 1
is not balanced.
There is no need to check the remaining nodes.
If even one node in a binary tree is not balanced, then the entire binary tree is not a balanced binary tree.
Therefore, this binary tree is an unbalanced binary tree
.
RELATED TAGS
CONTRIBUTOR
View all Courses