Complete vs full vs perfect binary trees in Data Structures Theory - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Identify the type of binary tree

Which of the following best describes a full binary tree?

A A tree where every node has either 0 or 2 children.

B A tree where all levels except possibly the last are completely filled, and all nodes are as far left as possible.

C A tree where all internal nodes have two children and all leaves are at the same level.

D A tree where every node has at most one child.

💡 Hint

Think about the number of children each node can have in a full binary tree.

A full binary tree is defined as a tree where every node has either zero or two children. This means no node has only one child.

🧠 Conceptual

intermediate

Characteristics of a complete binary tree

Which statement correctly describes a complete binary tree?

A All levels except possibly the last are completely filled, and all nodes in the last level are as far left as possible.

B All levels are fully filled, and all leaves are at the same depth.

C Every node has either 0 or 2 children.

D Every node has at most one child.

💡 Hint

Consider how nodes are arranged especially on the last level.

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

🧠 Conceptual

advanced

Perfect binary tree properties

Which of the following is true about a perfect binary tree?

A It is a tree where all levels except the last are filled, and the last level is filled from left to right.

B It is a tree where every node has at most one child.

C It is a full binary tree where all leaves are at the same level, and all internal nodes have two children.

D It is a tree where nodes can have any number of children.

💡 Hint

Think about both fullness and leaf level uniformity.

A perfect binary tree is a full binary tree where all leaves are at the same depth, meaning the tree is completely balanced.

❓ Comparison

advanced

Comparing tree types by node count

Given a binary tree with height h, which tree type guarantees exactly 2^(h+1) - 1 nodes?

A Complete binary tree

B Full binary tree

C Any binary tree

D Perfect binary tree

💡 Hint

Recall the formula for the number of nodes in a perfectly balanced tree.

A perfect binary tree of height h has exactly 2^(h+1) - 1 nodes because all levels are fully filled.

❓ Reasoning

expert

Determining tree type from node arrangement

You have a binary tree where every level except the last is fully filled, the last level is filled from left to right, but some nodes have only one child. What type of binary tree is this?

A Full binary tree

B Complete binary tree

C Perfect binary tree

D Neither complete, full, nor perfect

💡 Hint

Focus on the arrangement of nodes and the presence of nodes with only one child.

A complete binary tree allows nodes to have one child on the last level as long as nodes are filled left to right. Full binary trees do not allow nodes with only one child, and perfect binary trees require all leaves at the same level.