Complete vs full vs perfect binary trees in Data Structures Theory - Quick Revision & Key Differences

Recall & Review

beginner

What is a complete binary tree?

A complete binary tree is a tree where all levels are fully filled except possibly the last level, which is filled from left to right without gaps.

beginner

Define a full binary tree.

A full binary tree is a tree where every node has either 0 or 2 children. No node has only one child.

intermediate

What makes a binary tree perfect?

A perfect binary tree is both full and complete. All internal nodes have two children, and all leaf nodes are at the same level.

intermediate

How does a complete binary tree differ from a full binary tree?

A complete binary tree can have nodes with one child only at the last level, while a full binary tree does not allow any node to have only one child.

intermediate

Why is a perfect binary tree considered the most balanced?

Because all levels are fully filled and all leaves are at the same depth, making the tree symmetrical and balanced in height.

Which binary tree has all levels fully filled except possibly the last, which is filled from left to right?

A Full binary tree

B None of the above

C Perfect binary tree

D Complete binary tree

A complete binary tree fills all levels fully except possibly the last, which is filled from left to right.

In which binary tree does every node have either 0 or 2 children?

A Perfect binary tree

B Complete binary tree

C Full binary tree

D Skewed binary tree

A full binary tree requires every node to have either zero or two children.

Which binary tree is both full and complete with all leaves at the same level?

A Perfect binary tree

B Full binary tree

C Complete binary tree

D Balanced binary tree

A perfect binary tree is both full and complete, with all leaves at the same depth.

Can a complete binary tree have nodes with only one child?

A Yes, at any level

B Yes, but only at the last level

C No, never

D Only if it is also full

A complete binary tree can have nodes with one child only at the last level, filled from left to right.

Which property makes a perfect binary tree balanced?

A Both B and C

B All leaves are at the same level

C All levels are fully filled

D All nodes have two children

A perfect binary tree is balanced because all levels are fully filled and all leaves are at the same level.

Explain the differences between complete, full, and perfect binary trees.

Think about how nodes are arranged and how many children they have.

Why is a perfect binary tree considered more balanced than a complete or full binary tree?

Consider the shape and height of the tree.