A balanced binary tree is defined to be a tree such that heights of the two subtrees of any node never differ by more than one.
My question is what if one of the subtrees doesn't exist or basically the subtree is NULL
A balanced binary tree is defined to be a tree such that heights of the two subtrees of any node never differ by more than one.
My question is what if one of the subtrees doesn't exist or basically the subtree is NULL
An empty subtree counts as length 0. So if one subtree is empty, the other subtree must have depth 0 or 1. e.g. These are balanced trees:
A A
/ \ / \
B
but this is not:
A
/ \
B
/ \
C D
because the right subtree of A (B(C,D))
has depth 2 while the left subtree has depth 0.
The (B(C,D))
subtree itself is balanced, but the whole tree it's part of isn't.