Complete, full and perfect trees in arrays

Why this matters

Many tree questions are about shape, not about values. Does every node have either zero or two children? Are all the leaves at the same depth? Are the nodes packed to the left with no gaps? A shape question has a yes or no answer, and a short function can check it.

Shape also decides how a tree can be stored. A tree built from pointers needs one object for each node, plus a pointer for each child. A complete tree can live in a plain array with no pointers at all. The nodes sit in the array level by level, and simple arithmetic gives the parent or the children of any node. The heap lessons later in this course use the same trick, so this lesson is the base for them.

This lesson does not use the pointer tree from the earlier lessons. Every example uses an array where each position, called a slot, holds either a value or nothing. The code uses std::optional<int> for a slot, and the slots sit in a std::vector, a C++ array that can grow and that v[i] reads by slot number. An optional is a C++ type that holds either one value or an empty marker, and you ask it with has_value().

Words used in this lesson

A node is one spot in a tree that holds a value. The root is the top node, and it has no parent. A child is a node directly below another node, and the node above it is its parent. An edge is the line between a parent and a child.

A leaf is a node with no children. The level of a node is the number of edges between it and the root, so the root is on level 0, its children are on level 1, and so on. The height of a tree is the largest level that has a node in it. A tree with only a root has height 0.

A subtree is a node together with everything below it. The shape of a tree means how the nodes are connected, and the values do not change the shape.

Three shapes

Full

A full tree is a tree where every node has zero children or two children. A node with exactly one child breaks the rule.

      1
    /   \
   2     3
        / \
       4   5

Node 2 is a leaf. Node 3 has two children. Node 1 has two children. No node has exactly one child, so this tree is full.

Perfect

A perfect tree is full, every leaf is on the same level, and no spot is empty above the last level. A perfect tree of height 2 looks like this:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

A perfect tree of height 0 has 1 node. A perfect tree of height 1 has 3 nodes. A perfect tree of height 2 has 7 nodes. The next section shows why.

Complete

A complete tree has every level full except possibly the last one. On the last level, the nodes sit as far left as they can go, with no gap. Here is a complete tree:

      1
    /   \
   2     3
  /
 4

Level 1 is full, with nodes 2 and 3. Level 2 has one node, 4, placed at the far left. Node 2 has one child, so this tree is not full. It is also not perfect, because the leaf 3 is on a higher level than the leaf 4.

Here is a tree that is not complete:

      1
    /   \
   2     3
        / \
       4   5

Level 2 has nodes 4 and 5 under node 3. The spots under node 2 are empty, and they are to the left of 4. A gap on the left means the tree is not complete. This same tree is full, because node 2 is a leaf and node 3 has two children.

How the shapes relate

These are the facts to remember:

• A perfect tree is always full and always complete.
• A full tree is not always complete. The tree above with 4 and 5 under node 3 is full, but not complete.
• A complete tree is not always full. The tree with a single child under node 2 is complete, but not full.
• A tree can be none of the three. A straight line of three nodes, each one the child of the one above, is neither full nor complete.

Store a tree in an array

Slot numbers

Put the root in slot 0. Put the left child of the root in slot 1, and the right child in slot 2. The children of slot 1 go in slots 3 and 4. The children of slot 2 go in slots 5 and 6. The rule for any slot i is this:

• The left child of slot i is in slot 2i+1.
• The right child of slot i is in slot 2i+2.
• The parent of slot i is in slot (i-1)/2, using integer division. Integer division drops the fraction, so (4-1)/2 is 1. The root has no parent.

The slots fill one level after another, left to right. Level 0 holds slot 0. Level 1 holds slots 1 and 2. Level 2 holds slots 3 to 6. Level 3 holds slots 7 to 14. Each level has twice as many slots as the level above it, and it starts right after the last slot of the level above.

Why a complete tree needs no markers

The serialize lesson needed a # marker for each missing child, because it wrote a tree as one line of text. An array of slots can skip that step for a complete tree. In a complete tree, the nodes fill slots 0 to n-1 with no gap, where n is the number of nodes. A list of n values is the whole tree, and the length of the list is the node count.

A tree that is not complete needs holes. If a level has a gap, some slot in the middle of the array is empty, so the array needs an empty marker for it. That is why the code uses std::optional<int> for every slot. A complete tree is the case where the holes are gone.

Test each shape with code

The program below builds small trees from slots and runs five checks on each one. Each check is a function.

• filled(t, i) says whether slot i is inside the array and holds a value. It checks the range first, so it never reads past the end of the array.
• isValidTree(t) says whether every filled slot, except the root, has a filled parent. An array with a value in slot 1 and nothing in slot 0 is not a tree.
• isFull(t) checks each filled slot. Its two children must both be filled, or both be empty.
• isComplete(t) counts the nodes n, then checks that slots 0 to n-1 are all filled. If there are n nodes and the first n slots are all filled, nothing is left over.
• isPerfect(t) is complete, and the node count plus one is a power of 2. A perfect tree of height h has 2^(h+1)-1 nodes, so n+1 is 2^(h+1). The function std::has_single_bit is true for a power of 2.

Save this as shapes.cpp:

#include <bit>
#include <cstddef>
#include <iostream>
#include <optional>
#include <string>
#include <vector>
 
// Slot i holds the node with index i, or nothing when the spot is empty.
// Left child of slot i is slot 2i+1, right child is slot 2i+2.
using Slots = std::vector<std::optional<int>>;
 
std::size_t leftOf(std::size_t i) { return 2 * i + 1; }
std::size_t rightOf(std::size_t i) { return 2 * i + 2; }
 
bool filled(const Slots& t, std::size_t i) {
    return i < t.size() && t[i].has_value();
}
 
std::size_t countNodes(const Slots& t) {
    std::size_t n = 0;
    for (const auto& s : t) {
        if (s) ++n;
    }
    return n;
}
 
// Every filled slot except the root must have a filled parent.
bool isValidTree(const Slots& t) {
    for (std::size_t i = 1; i < t.size(); ++i) {
        if (filled(t, i) && !filled(t, (i - 1) / 2)) return false;
    }
    return true;
}
 
// Every node has 0 or 2 children.
bool isFull(const Slots& t) {
    for (std::size_t i = 0; i < t.size(); ++i) {
        if (!filled(t, i)) continue;
        if (filled(t, leftOf(i)) != filled(t, rightOf(i))) return false;
    }
    return true;
}
 
// The nodes fill slots 0 .. n-1 with no gap.
bool isComplete(const Slots& t) {
    std::size_t n = countNodes(t);
    for (std::size_t i = 0; i < n; ++i) {
        if (!filled(t, i)) return false;
    }
    return true;
}
 
// Complete, and the node count is 2^k - 1 for some k (1, 3, 7, 15, ...).
bool isPerfect(const Slots& t) {
    std::size_t n = countNodes(t);
    return n > 0 && isComplete(t) && std::has_single_bit(n + 1);
}
 
std::string shape(const Slots& t) {
    std::string s;
    if (isPerfect(t)) s += "perfect ";
    if (isFull(t)) s += "full ";
    if (isComplete(t)) s += "complete ";
    if (s.empty()) s = "neither ";
    if (!isValidTree(t)) s = "NOT A TREE ";
    return s;
}
 
void show(const std::string& name, const Slots& t) {
    std::cout << name << " (" << countNodes(t) << " nodes): "
              << "valid=" << std::boolalpha << isValidTree(t)
              << " full=" << isFull(t)
              << " complete=" << isComplete(t)
              << " perfect=" << isPerfect(t) << "  -> " << shape(t) << "\n";
}
 
int main() {
    show("one node      ", {1});
    show("chain         ", {1, 2, std::nullopt, 3});
    show("full, not comp", {1, 2, 3, std::nullopt, std::nullopt, 4, 5});
    show("full+complete ", {1, 2, 3, 4, 5});
    show("perfect 7     ", {1, 2, 3, 4, 5, 6, 7});
    show("complete only ", {1, 2, 3, 4});
    show("neither       ", {1, std::nullopt, 2});
    show("gap at root   ", {std::nullopt, 5});
}

Compile and run it:

g++ -std=c++20 -Wall -o shapes shapes.cpp && ./shapes

The output is:

one node       (1 nodes): valid=true full=true complete=true perfect=true  -> perfect full complete 
chain          (3 nodes): valid=true full=false complete=false perfect=false  -> neither 
full, not comp (5 nodes): valid=true full=true complete=false perfect=false  -> full 
full+complete  (5 nodes): valid=true full=true complete=true perfect=false  -> full complete 
perfect 7      (7 nodes): valid=true full=true complete=true perfect=true  -> perfect full complete 
complete only  (4 nodes): valid=true full=false complete=true perfect=false  -> complete 
neither        (2 nodes): valid=true full=false complete=false perfect=false  -> neither 
gap at root    (1 nodes): valid=false full=true complete=false perfect=false  -> NOT A TREE 

Read the rows against the pictures in the first part of the lesson. The "chain" row is the line of three nodes with each node on the left. It has an empty slot 2, while slot 3 is filled, so it is not complete. The "full, not comp" row is the tree with 4 and 5 under node 3. The "perfect 7" row has 7 nodes, and 7 + 1 is 8, which is a power of 2.

The "gap at root" row has a value in slot 1 and nothing in slot 0. No root means the array does not describe a tree, so the other answers do not apply. The shape function prints NOT A TREE in that case.

The code treats the empty array as full and complete, and it does not call it perfect. Some courses and libraries count the empty tree as perfect, so check the rule you are given before you write a test.

Why the perfect check is so short

A perfect tree of height h has 2^(h+1)-1 nodes. So the node count n of a perfect tree is always one less than a power of 2. The reverse is also true, if the tree is complete. A complete tree with n = 2^k - 1 nodes fills slots 0 to n-1, and those slots are exactly the levels 0 to k-1, all full. So a complete tree is perfect when its node count plus one is a power of 2. The code does not need to count the nodes on each level.

Count nodes from height

Height and node count are linked. Knowing one tells you a range for the other. These facts come from the level sizes.

A perfect tree of height h has h+1 levels, and level k holds 2^k nodes. Add them up: 1 + 2 + 4 + ... + 2^h equals 2^(h+1) - 1. A complete tree of height h has all of its levels full above the last one, so it has at least 2^h nodes (the full levels above the last one, plus one node on the last level). It has at most 2^(h+1) - 1 nodes, which is the perfect count.

The reverse question is more useful in practice. Given the node count of a complete tree, what is its height? The height is the number of times you can halve the count, rounded down, which is written floor(log2 n). The function std::bit_width gives a quicker answer. It returns how many binary digits a number needs. For example, 10 is 1010 in binary, which has 4 digits, so the height is 4 - 1 = 3.

The next program uses that rule. It also prints the table above from the code, so you can check the numbers.

#include <bit>
#include <cstddef>
#include <iostream>
 
int main() {
    for (std::size_t count : {1, 2, 3, 4, 7, 8, 10, 15, 16}) {
        std::size_t h = std::bit_width(count) - 1;
        std::cout << "  " << count << " nodes -> height " << h << "\n";
    }
    for (std::size_t h = 0; h <= 4; ++h) {
        std::size_t minComplete = std::size_t{1} << h;
        std::size_t maxAny = (std::size_t{1} << (h + 1)) - 1;
        std::cout << "  height " << h << ": complete " << minComplete << ".." << maxAny
                  << ", perfect exactly " << maxAny << "\n";
    }
}

The output is:

  1 nodes -> height 0
  2 nodes -> height 1
  3 nodes -> height 1
  4 nodes -> height 2
  7 nodes -> height 2
  8 nodes -> height 3
  10 nodes -> height 3
  15 nodes -> height 3
  16 nodes -> height 4
  height 0: complete 1..1, perfect exactly 1
  height 1: complete 2..3, perfect exactly 3
  height 2: complete 4..7, perfect exactly 7
  height 3: complete 8..15, perfect exactly 15
  height 4: complete 16..31, perfect exactly 31

A full tree is a different case. Its node count is always odd. Each node that has children adds exactly two children. If the tree has k such nodes, the children number 2k, and adding the root gives 2k + 1. This is a quick check for a bad input: a tree with an even, non-zero node count can never be full.

Worked examples

Example 1: check one array by hand

Take the array {1, 2, 3, nullopt, nullopt, 4, 5}. Write it with slot numbers first.

Step 1: Is it a valid tree? Slot 5 has a parent in slot 2, and slot 6 has a parent in slot 2. Slot 1 has a parent in slot 0. Every filled slot has a filled parent, so it is valid.

Step 2: Is it full? Slot 0 has children in slots 1 and 2, both filled. Slot 1 has children in slots 3 and 4, both empty, so it is a leaf. Slot 2 has children in slots 5 and 6, both filled. Every node has zero or two children, so it is full.

Step 3: Is it complete? It has 5 nodes. Slots 0 to 4 must be filled, and slot 3 is empty. It is not complete.

The answer is full, not complete. The program prints the same row, under the name "full, not comp".

Example 2: index math on a complete tree

Take the ten values 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 in a std::vector<int>. There are no empty slots, because the tree is complete. Here is a program that prints the children and parent of each slot:

#include <cstddef>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> t = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    std::size_t n = t.size();
 
    std::cout << "slot  value  left(slot)  right(slot)  parent(slot)\n";
    for (std::size_t i = 0; i < n; ++i) {
        std::cout << "  " << i << "    " << t[i] << "     ";
        std::size_t l = 2 * i + 1;
        std::size_t r = 2 * i + 2;
        if (l < n) std::cout << t[l] << "(" << l << ")";
        else       std::cout << "-";
        std::cout << "        ";
        if (r < n) std::cout << t[r] << "(" << r << ")";
        else       std::cout << "-";
        std::cout << "        ";
        if (i == 0) std::cout << "none";
        else        std::cout << t[(i - 1) / 2] << "(" << (i - 1) / 2 << ")";
        std::cout << "\n";
    }
}

The output is:

slot  value  left(slot)  right(slot)  parent(slot)
  0    10     20(1)        30(2)        none
  1    20     40(3)        50(4)        10(0)
  2    30     60(5)        70(6)        10(0)
  3    40     80(7)        90(8)        20(1)
  4    50     100(9)        -        20(1)
  5    60     -        -        30(2)
  6    70     -        -        30(2)
  7    80     -        -        40(3)
  8    90     -        -        40(3)
  9    100     -        -        50(4)

Take slot 4, which holds 50. Its left child is slot 2*4+1 = 9, which holds 100. Its right child would be slot 2*4+2 = 10, but the array has only 10 slots (0 to 9), so there is no right child. Its parent is slot (4-1)/2 = 1, which holds 20. The table agrees: 50 is the right child of 20.

Notice that the program checks l < n before it reads t[l]. The index formulas can point past the end of the array, and the check is what keeps the program safe.

Example 3: add to a complete array

A complete tree can grow by adding one value at the end of the array. The new node goes to the first empty spot in level order, which is slot n-1 for the new count n. The new node's parent is slot (n-2)/2. The shape stays complete, so the tree never needs a hole.

#include <bit>
#include <cstddef>
#include <iostream>
#include <vector>
 
int main() {
    // A complete tree with 6 nodes. Add a value at the next free slot.
    std::vector<int> values = {1, 2, 3, 4, 5, 6};
    std::cout << "start: " << values.size() << " nodes, height " << std::bit_width(values.size()) - 1 << "\n";
 
    // Adding to the end of the array adds the node at the first empty spot
    // in level order, so the tree stays complete.
    for (int extra : {7, 8}) {
        values.push_back(extra);
        std::size_t n = values.size();
        std::size_t parent = (n - 1 - 1) / 2;
        std::cout << "added " << extra << " at slot " << n - 1 << ", parent slot " << parent
                  << " (value " << values[parent] << "), height " << std::bit_width(n) - 1 << "\n";
    }
}

The output is:

start: 6 nodes, height 2
added 7 at slot 6, parent slot 2 (value 3), height 2
added 8 at slot 7, parent slot 3 (value 4), height 3

The height goes up at the moment the count reaches a power of 2. Going from 7 nodes to 8 nodes adds a new level, so the height goes from 2 to 3. Seven nodes is a perfect tree of height 2, and adding an eighth node starts level 3.

Common mistakes

Using 2i and 2i+1 with slots that start at 0

The children formulas must be 2i+1 and 2i+2 when the root is in slot 0. A common error is to copy the formulas from a 1-based array, where the root is in slot 1 and the children are 2i and 2i+1. With slots that start at 0, the left child of slot 0 would be slot 0 itself. A walk from parent to child would then never reach the bottom of the tree. Nothing in the compiler will flag this, so write the formula down once and test it on the table of slots above.

Parent of the root with unsigned numbers

The index type std::size_t cannot hold a negative number. So (i - 1) / 2 with i equal to 0 does not give -1 divided by 2. It wraps around to a huge number. The next program shows the effect:

#include <cstddef>
#include <iostream>
#include <limits>
 
int main() {
    std::size_t root = 0;
    std::size_t wrongParent = (root - 1) / 2;
    std::cout << "(0 - 1) / 2 with size_t = " << wrongParent << "\n";
    std::cout << "largest size_t = " << std::numeric_limits<std::size_t>::max() << "\n";
}

The output is:

(0 - 1) / 2 with size_t = 9223372036854775807
largest size_t = 18446744073709551615

The wrong parent is about 9 quintillion, far outside the array. The fix is to check i > 0 before computing the parent. The isValidTree function in the shape program does this by starting its loop at i = 1.

Reading an empty slot as a number

A slot of type std::optional<int> is not an int. Assigning it straight to an int fails to compile. This is the error the compiler printed for the line int x = t[0];, where t is a std::vector<std::optional<int>>:

mistakes_compile.cpp: In function ‘int main()’:
mistakes_compile.cpp:9:16: error: cannot convert ‘__gnu_cxx::__alloc_traits<std::allocator<std::optional<int> >, std::optional<int> >::value_type’ {aka ‘std::optional<int>’} to ‘int’ in initialization
    9 |     int x = t[0];
      |                ^

The wording and line numbers depend on the compiler, so yours may differ. Read the phrase to 'int' in initialization. It means the left side expects an int and the right side is an optional. Check has_value() first, then read the value.

Going past the end of the array

The [] operator on a std::vector does not check the index. Reading past the end is undefined behavior, which means the program may print a wrong value, crash, or appear to work. The at() function checks the index and throws an exception (an error that stops the program unless the code catches it) when it is out of range. This is the message from a program that asked for slot 9 in a 7-slot array with t.at(2 * i + 1):

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 9) >= this->size() (which is 7)

The message names the index, 9, and the size, 7. In a tree program, the index almost always comes from a formula like 2i+1. Look at that formula first when you see this message.

Testing perfect by the node count alone

A tempting test is to say a tree is perfect when its node count is a power of 2. That is wrong. A tree with 4 nodes has a count that is a power of 2, but it cannot be perfect, because a perfect tree has 1, 3, 7, 15, and so on nodes. The test must use n + 1. In the shapes program, the complete only row has 4 nodes and perfect=false.

Using the array size as the node count

A std::vector with holes still has a size. The size counts the empty slots too. In the array {1, 2, nullopt, 4, 5}, the size is 5, and the node count is 4. Use countNodes to get the node count, and do not use size() when the array may have holes.

Practice

Use the shape functions from this lesson for each exercise. Write each answer on paper before you check it.

1. The array is {1, 2, nullopt, 4, 5}. Is it complete? Is it full? Is it perfect?

Show the answer

No, no, and no. Slot 2 is empty, but slots 3 and 4 are filled, so the tree is not complete. Slot 0 has a left child (slot 1) and no right child (slot 2), so it is not full. A tree with 4 nodes cannot be perfect. isFull, isComplete and isPerfect all return false for this array.

2. In a complete tree, what are the parent of slot 11 and the two children of slot 3?

Show the answer

The parent of slot 11 is slot 5, because (11-1)/2 is 5. The children of slot 3 are slots 7 and 8, because 2*3+1 is 7 and 2*3+2 is 8.

3. A complete tree has height 4. How many nodes can it have?

Show the answer

It can have from 16 to 31 nodes. The lowest count is 2^4, because levels 0 to 3 are full and the last level needs one node. The highest count is 2^5 - 1, which is a perfect tree of height 4.

4. A complete tree has 13 nodes. What is its height?

Show the answer

The height is 3. The number 13 is 1101 in binary, which has 4 digits, so std::bit_width(13) is 4, and the height is 4 - 1. Levels 0 to 2 hold 7 nodes, and the last level holds the other 6.

5. Which of the counts 3, 4 and 5 can be a perfect tree?

Show the answer

Only 3. A perfect tree has 2^(h+1) - 1 nodes, which gives 1, 3, 7, 15, and so on. isPerfect returns true for three nodes and false for four and five nodes.

Summary

• A full tree has every node with zero or two children. A perfect tree is full, complete, and has every leaf on the same level. A complete tree fills each level before starting the next one, and packs the last level to the left.
• In an array, the root is in slot 0. The children of slot i are slots 2i+1 and 2i+2, and the parent of slot i is slot (i-1)/2.
• A complete tree fills slots 0 to n-1 with no gap, so it needs no empty markers. A tree with a gap needs std::optional slots.
• A perfect tree has 2^(h+1) - 1 nodes. A complete tree of height h has from 2^h to 2^(h+1) - 1 nodes.
• The height of a complete tree with n nodes is std::bit_width(n) - 1.
• Check the parent index before you use it, and check the child index against the size of the array before you read it.