Definition of complete binary tree

0
votes

(From: Data Structures Using C By Aaron M. Tenenbaum):

"A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d."

So, by that meaning the following tree should not be complete binary tree, right?

http://cs-study.blogspot.de/2012/11/complete-binary-tree.html

But, it is according to wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.

Please clarify my confusion.

1
data-structurestreelanguage-agnosticbinary-tree

1 Answers

0
votes

My interpretation:

  • On level 1..d-1 there are only nodes, and all of them must exist.
  • At level d, only leaves exists, and they must be filled from left to right
  • Nodes without children are not considered leaves on level d-1