What is a complete tree?
We have read about trees, binary trees, binary search trees - but what are these complete trees, lets figure out that now.
In the tutorial below, I'll go through the basics which will explain the fundamentals about Complete Trees. Keep in mind, complete trees and binary trees are building blocks for a HEAP.
When a complete binary tree is built, its nodes are generally added one at a time.
As with any tree, the first node must be the root.
The second node of a complete binary tree is always the left child of the root...
... and the third node is always the right child of the root. And so we continue, adding nodes.
But in a complete binary tree, the way that we add nodes is restricted: Nodes must completely fill each level from left-to-right before proceeding to the next level.
A Correct Complete Tree >
/ \ /
1 4 7
An Incorrect Complete Tree >
Nodes must completely fill each level from left-to-right before proceeding to the next level. 5 should be started with children first before assigning children to 2.
Again, an Incorrect Complete Tree >;
Nodes must completely fill each level from left-to-right before proceeding to the next level. Right Node of 2 must be filled first before starting with children of 8.
Another Correct Complete Tree >;
Hey, but where is the tree???
Empty tree is also a complete tree!