0
votes

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

1
Then in that case the different will be 1. Still falls in the definitionRahul Arora
So a linked list is a balanced binary tree?itachi_uchiha
What makes you think being one subtree null differ by more than one?Sazzad Hissain Khan

1 Answers

2
votes

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.