Bird
Raised Fist0
Data Structures Theoryknowledge~5 mins

Complete vs full vs perfect binary trees in Data Structures Theory - Performance Comparison

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: Complete vs full vs perfect binary trees
O(n)
Understanding Time Complexity

When working with different types of binary trees, it helps to understand how their structure affects the time it takes to perform operations like searching or inserting.

We want to see how the shape of complete, full, and perfect binary trees influences the number of steps needed as the tree grows.

Scenario Under Consideration

Analyze the time complexity of searching for a value in these binary trees.


function searchInBinaryTree(root, target) {
  if (root == null) return false;
  if (root.value === target) return true;
  return searchInBinaryTree(root.left, target) || searchInBinaryTree(root.right, target);
}

This code searches for a value by checking nodes recursively in a binary tree.

Identify Repeating Operations

Look at what repeats as the tree grows:

  • Primary operation: Visiting each node once during the search.
  • How many times: Up to every node in the tree, depending on where the target is.
How Execution Grows With Input

As the number of nodes (n) increases, the search may need to check more nodes.

Input Size (n)Approx. Operations (Nodes Visited)
10Up to 10
100Up to 100
1000Up to 1000

Pattern observation: The search could visit every node in the worst case, so the work grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "All binary trees have the same search speed because they have the same number of nodes."

[OK] Correct: The shape matters; perfect trees are balanced and can allow faster operations, while complete or full trees might be less balanced, affecting search steps.

Interview Connect

Understanding these tree types helps you explain how data structure shape affects performance, a key skill in coding interviews and real projects.

Self-Check

"What if the binary tree was always perfect and balanced? How would that change the time complexity of searching?"

Practice

(1/5)
1. Which of the following best describes a full binary tree?
easy
A. All levels are completely filled, including the last level.
B. Every node has either 0 or 2 children, no nodes have only one child.
C. All leaves are at the same level and every internal node has two children.
D. Nodes at the last level are as far right as possible.

Solution

  1. Step 1: Understand the definition of a full binary tree

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

  2. Step 2: Compare with other tree types

    Complete binary trees focus on filling levels left to right, and perfect binary trees are both full and complete with all leaves at the same level.

  3. Final Answer:

    Every node has either 0 or 2 children, no nodes have only one child. -> Option B

  4. Quick Check:

    Full binary tree = nodes have 0 or 2 children [OK]
Hint: Full means nodes have 0 or 2 children only [OK]
Common Mistakes:
  • Confusing full with complete trees
  • Thinking full means all levels filled
  • Assuming nodes can have one child
2. Which property must a perfect binary tree always satisfy?
easy
A. All levels except the last are completely filled, and last level nodes are left aligned.
B. Nodes at the last level can be anywhere, not necessarily left aligned.
C. Every node has at most one child.
D. Every node has either 0 or 2 children, and all leaves are at the same level.

Solution

  1. Step 1: Recall the definition of a perfect binary tree

    A perfect binary tree is both full and complete, meaning every node has 0 or 2 children and all leaves are at the same level.

  2. Step 2: Eliminate incorrect options

    All levels except the last are completely filled, and last level nodes are left aligned. describes a complete tree, not necessarily perfect. Nodes at the last level can be anywhere, not necessarily left aligned. contradicts the left alignment rule. Every node has at most one child. is incorrect as perfect trees have nodes with two children.

  3. Final Answer:

    Every node has either 0 or 2 children, and all leaves are at the same level. -> Option D

  4. Quick Check:

    Perfect tree = full + all leaves same level [OK]
Hint: Perfect = full + all leaves at same level [OK]
Common Mistakes:
  • Mixing complete and perfect tree definitions
  • Ignoring leaf level uniformity
  • Assuming last level nodes can be scattered
3. Consider the following binary tree structure:
       A
      / \
     B   C
    / 
   D

Which type of binary tree is this?
medium
A. Complete binary tree
B. Full binary tree
C. Perfect binary tree
D. None of the above

Solution

  1. Step 1: Analyze the tree structure

    The tree has root A with two children B and C. Node B has one child D. Node C has no children.

  2. Step 2: Check properties against tree types

    Node B has exactly one child, so it is not full (full requires every node has 0 or 2 children). Levels 0 and 1 are completely filled; level 2 has D as far left as possible: complete. Leaves C (level 1) and D (level 2) not same level: not perfect.

  3. Final Answer:

    Complete binary tree -> Option A

  4. Quick Check:

    Last level left aligned but not full = complete tree [OK]
Hint: Complete trees fill left to right, full requires 0 or 2 children [OK]
Common Mistakes:
  • Assuming missing right child means not complete
  • Confusing full with complete
  • Thinking perfect applies without full and complete
4. Identify the error in the following statement:
A perfect binary tree can have nodes with only one child.
medium
A. Incorrect, perfect trees require all internal nodes to have two children.
B. Correct statement, perfect trees allow one child nodes.
C. Incorrect, perfect trees only require last level to be full.
D. Correct, as long as the tree is complete.

Solution

  1. Step 1: Understand perfect binary tree requirements

    Perfect binary trees are both full and complete, meaning every internal node must have exactly two children.

  2. Step 2: Evaluate the statement

    The statement claims nodes can have only one child, which contradicts the full tree property required for perfect trees.

  3. Final Answer:

    Incorrect, perfect trees require all internal nodes to have two children. -> Option A

  4. Quick Check:

    Perfect tree = no single-child nodes [OK]
Hint: Perfect trees never have single-child nodes [OK]
Common Mistakes:
  • Confusing complete with perfect tree rules
  • Thinking one child allowed if tree is complete
  • Ignoring full tree property in perfect trees
5. You have a binary tree with 15 nodes. It is known to be a perfect binary tree. How many leaf nodes does it have?
hard
A. 7
B. 16
C. 8
D. 15

Solution

  1. Step 1: Recall leaf count formula for perfect binary trees

    In a perfect binary tree, the number of leaf nodes is (n + 1) / 2, where n is the total number of nodes.

  2. Step 2: Calculate leaf nodes for 15 nodes

    Using the formula: (15 + 1) / 2 = 16 / 2 = 8 leaf nodes.

  3. Final Answer:

    8 -> Option C

  4. Quick Check:

    Leaf nodes = (total nodes + 1) / 2 = 8 [OK]
Hint: Perfect tree leaves = (nodes + 1) / 2 [OK]
Common Mistakes:
  • Using total nodes as leaf count
  • Confusing full and perfect tree leaf counts
  • Forgetting leaf count formula