Left balanced binary trees

Question

I am reading a book on data structures and it says that a left balanced binary tree is a tree in which the leaves only occupy the leftmost positions in the last level.

This seemed a little vague to me. Does this mean that leaves are only on the left side of a root and are distributed throughout the whole level, or leave exists only on the left side of the entire tree. Exactly what constitute left balanced?

I am not sure if my guess even covers any of the answer, so if anyone could help, it would be greatly appreciated :-).

Answer 1

You can think of a left-balanced binary tree as a balanced binary tree where the left sub-tree of each node is filled before the right sub-tree. In more informal terms, this is a tree wherein the nodes at the bottom-most level are all on the left side of the entire tree.

Take this tree for example:

This tree is balanced, but not left-balanced. If node 67 were removed, however, the tree would be left-balanced.

Answer 2

I don't really know the answer, but based on the description in the book it sounds to me like this...

For starters, lets think of it this way. Every "row" in the tree has a number, starting at zero and counting up. The row with the highest number is considered to be the last level.

Remember that leaf nodes are nodes without any children. So the tree meets the condition that every leaf node in the last level must be on the left, like so:

          50
       /     \
     /         \
    35         70
   /  \       /  \
 10    34    57  90
 /     /        /
9     7        78

If we were to add a "98" as the right-child of 90 or a "59" as the right-child of 57, then this tree would no longer be left-balanced.

---

Edit: After reading Brandon E Taylor's answer, you should definitely not choose this one. After looking it over and reading the description again, not only does his make more sense, but it fits the description much better.

Answer 3

It seems to me that the definition of left balanced binary tree is the same of complete binary tree.