Definition of a Balanced Tree

I am just wondering if someone might be able to clarify the definition of a balanced tree for me. I have that “a tree is balanced if each sub-tree is balanced and the height of the two sub-trees differ by at most one.

I apologize if this is a dumb question, but does this definition apply to every node all the way down to the leaves of a tree or only to the left and right sub-trees immediately off the root? I guess another way to frame this would be, is it possible for internal nodes of a tree to be unbalanced and the whole tree to remain balanced?

Leave a Comment