Why this matters
A binary tree is a set of nodes. Each node holds a value and has at most two child links, called left and right. Trees come in shapes, and three shape names appear often in courses, interviews and library code: full, complete and perfect. Each name has an exact rule. If you know the rule, you can test a tree in a few lines of code.
The shape also decides how you can store the tree. A complete tree can be stored in a plain list with no node objects and no child links at all. Python's heapq module keeps its heap in a list this way, and it finds the children of an entry with the same index math used in this lesson.
The earlier lessons in this module covered traversal orders and building trees from lists of values. This lesson looks at the shape of a tree and at its list form.
Words we need
A node is one box in the tree. A leaf is a node with no children. A child link points from a node to one of its children. An edge is the line between a node and a child.
The height of a tree is the number of edges on the longest path from the root down to a leaf. A single node has height 0. In this lesson an empty tree has height -1, so that the formulas below work for every tree, including the empty one.
A level is a row of nodes that are the same distance from the root. The root is on level 0, its children are on level 1, and so on.
The three shapes
A full tree is a tree where every node has zero children or two children. No node has exactly one child.
A complete tree is a tree where every level is filled from left to right, except possibly the last level. On the last level the nodes stay on the left, and there is no gap before them.
A perfect tree is a tree where every node that has children has exactly two, and every leaf is on the same level.
Here is one example of each, drawn with the node values as labels.
Perfect (7 nodes) Full and complete (5 nodes) Complete, not full (6 nodes)
1 1 1
/ \ / \ / \
2 3 2 3 2 3
/ \ / \ / \ / \ /
4 5 6 7 4 5 4 5 6The middle tree is full, because node 3 has no children and every other node has two. It is complete, because level 2 is filled from the left with no gap. It is not perfect, because leaf 3 is on level 1 while leaves 4 and 5 are on level 2. The right tree is complete, because its last level is filled from the left with no gap. It is not full, because node 3 has one child, on its left.
Every perfect tree is also full and complete. Not every full tree is complete, and not every complete tree is full.
Building a tree from a list
To test the shapes we need trees. The easiest way to write a tree in code is a list that lists the nodes level by level, from left to right. Use None for a missing node.
The list positions have a fixed pattern, called index math:
- The root is at index 0.
- The left child of index
iis at2 * i + 1. - The right child of index
iis at2 * i + 2. - The parent of index
iis at(i - 1) // 2, using integer division, which drops the remainder.
The function below builds a tree from such a list. It starts at an index and makes a node if the value there is not None. Then it builds the left and right children from their index formulas.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def from_list(values, i=0):
if i >= len(values) or values[i] is None:
return None
node = TreeNode(values[i])
node.left = from_list(values, 2 * i + 1)
node.right = from_list(values, 2 * i + 2)
return nodeThe list [1, 2, 3, 4, 5, None, 6] gives the sample tree from the earlier lessons. Index 5 is None, so node 3 has no left child. Index 6 holds 6, which is the right child of index 2, the node with value 3.
A note on this function: if a position is None, the function never looks at the positions below it. A value that sits under a None is ignored. Keep this in mind for the list checks later in the lesson.
Testing each shape
Full
A tree is full when no node has exactly one child. The test is a recursion. An empty tree is full, a node with one child is not, and a node with two children is full only if both of its subtrees are full.
def is_full(node):
if node is None:
return True
if (node.left is None) != (node.right is None):
return False
return is_full(node.left) and is_full(node.right)The line with != is the core of the test. It is true when exactly one side is missing. The != on two bool values (each one is True or False) checks whether they differ, so the line means: one child is missing and the other is not.
Complete
A tree is complete when the nodes can be read level by level, left to right, with no gap. The simplest test walks the tree in level order, which is the same order the nodes appear in the list. The walk uses a queue, a line of items that come out in the order they went in. When it reaches a missing child, it records a gap. If it then reaches a real node, the tree is not complete.
from collections import deque
def is_complete(root):
queue = deque([root])
seen_gap = False
while queue:
node = queue.popleft()
if node is None:
seen_gap = True
continue
if seen_gap:
return False
queue.append(node.left)
queue.append(node.right)
return TrueThe queue holds None entries on purpose. A missing child is added as None, so the walk can see the gap. A deque accepts None as an item, so the walk works without any special setup. The mistakes section shows why the check on None must come before any attribute is read.
Perfect
A perfect tree of height h has exactly 2^(h+1) - 1 nodes. Level 0 has 1 node, level 1 has 2, level 2 has 4, and each level has twice as many as the one above. The total is 1 + 2 + 4 + ... up to level h, which is 2^(h+1) - 1.
No tree of height h can have more nodes than that, because each level has at most twice the nodes of the level above. So the test is simple. Measure the height, count the nodes, and compare. If the count equals 2^(h+1) - 1, every level must be full, and the tree is perfect.
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
def is_perfect(root):
h = height(root)
return count_nodes(root) == (1 << (h + 1)) - 1The expression 1 << (h + 1) means 2 raised to the power h + 1. The << operator moves the bits of the number left, and each move doubles the value. For an empty tree, h is -1, so 1 << 0 is 1 and the expected count is 0, which is correct.
Running all three tests
The program below builds a set of lists, converts each one to a tree, and prints the result of the three tests. The last two columns show the node count and the height.
Output:
perfect full=True complete=True perfect=True nodes=7 height=2
full-not-perf full=True complete=True perfect=False nodes=5 height=2
complete-only full=False complete=True perfect=False nodes=6 height=2
sample full=False complete=False perfect=False nodes=6 height=2
chain full=False complete=False perfect=False nodes=3 height=2
single full=True complete=True perfect=True nodes=1 height=0
empty full=True complete=True perfect=True nodes=0 height=-1Read the rows one at a time. The full-not-perf row is full and complete, but it has 5 nodes at height 2, and a perfect tree of that height needs 7. The complete-only row has a node with one child, so it is not full. The chain row is a line of three nodes, going left then left again. It is not full, because node 1 has one child. It is not complete, because the list [1, 2, None, 3] has a value at index 3 after the None at index 2.
The empty tree is full, complete and perfect. That is the usual convention, and the formulas agree with it.
Counting nodes from the height
The perfect rule gives the count directly, but the same idea works for any complete tree. A complete tree of height h has every level from 0 to h - 1 filled, and the last level, level h, has at least one node and at most 2^h nodes.
The filled levels hold 1 + 2 + ... + 2^(h-1), which is 2^h - 1 nodes. Adding the last level gives a total between 2^h and 2^h - 1 + 2^h, which is 2^(h+1) - 1.
So a complete tree of height h has at least 2^h nodes and at most 2^(h+1) - 1. Turned around, the height of a complete tree with n nodes is the number of times you can halve n and still get 1 or more. That is the base 2 logarithm of n, rounded down: the largest h with 2^h at most n. Python has a fast way to compute it, the method bit_length:
def height_of_complete(n):
return n.bit_length() - 1n.bit_length() gives the number of bits needed to write n in binary. For n = 8, which is 1000 in binary, that is 4, and subtracting 1 gives height 3. For n = 0 it returns -1, which matches the height of an empty tree.
Storing a complete tree in a list
A complete tree has no gaps, so its list has no None entries before the last node. Every position from 0 to n - 1 holds a node. The index math from earlier gives every link, so the node objects and the child attributes are not needed.
Take six nodes, with the values 10, 20, 30, 40, 50 and 60 in level order.
10 index 0
/ \
20 30 indices 1 and 2
/ \ /
40 50 60 indices 3, 4 and 5The position of each value is its index. The children of 20 (index 1) are at indices 3 and 4, which hold 40 and 50. The children of 30 (index 2) are at 5 and 6, but 6 is past the end of the list, so 30 has one child, 60.
The program below prints the index math for the first seven positions, so you can check each row by hand.
Output:
parent(0)=-1
i=0 left=1 right=2 parent=-1
i=1 left=3 right=4 parent=0
i=2 left=5 right=6 parent=0
i=3 left=7 right=8 parent=1
i=4 left=9 right=10 parent=1
i=5 left=11 right=12 parent=2
i=6 left=13 right=14 parent=2The root has no parent, and parent(0) returns -1 here, because Python's // rounds toward negative infinity. The value -1 is not a real index, so a loop that walks up must stop before it. The mistakes section shows what happens when it does not.
The same index math gives a rule for the leaves. In a tree with n positions, index i has a left child only if 2 * i + 1 < n. This means index i is a leaf exactly when i >= n // 2. For n = 6, indices 3, 4 and 5 are leaves, which matches the picture above. For n = 7, indices 3, 4, 5 and 6 are leaves.
The height of the list tree is the same number as before: n.bit_length() - 1. For n = 6 the height is 2.
Checking the list form
When the input is a list, you can test completeness without building nodes. The rule is that a complete tree in list form has no None before the last real value. Once a None appears, every later position must also be None.
def is_complete_list(a):
seen_none = False
for v in a:
if v is None:
seen_none = True
elif seen_none:
return False
return TrueThis check needs one rule about the input. Every non-None value must have a non-None parent. The check does not look at parents, so [None, 1] is treated as not complete, because the value 1 follows a None. A list that breaks the rule can give the wrong answer, so use this check on lists that are a fair picture of a tree.
I tested the check against the node-based is_complete on random lists of length 1 to 12. The random lists were kept only when they are a fair picture of a tree, meaning every non-None value has a non-None parent. The two checks agreed on every list kept.
Worked examples with increasing difficulty
Example 1: a short list
Is [1, 2, 3, 4, None, 5, 6] a complete tree?
Walk the list. Index 0 holds 1, index 1 holds 2, index 2 holds 3, index 3 holds 4. Index 4 holds None, which is the first gap. Index 5 holds 5, which comes after the gap, so the answer is no.
The node-based tests agree: this tree is not full, not complete and not perfect. Node 2 has a left child 4 and no right child, so it is not full. The gap at index 4 comes before the real node 5, so it is not complete.
Example 2: a longer complete tree
Is [1, 2, 3, 4, 5, 6, 7, 8] complete, and what is its height?
It has no None entries, so the list check says yes. The node count is 8, and (8).bit_length() - 1 is 3. The height is 3. Level 3 holds only node 8, which sits at the far left. The tree is complete. It is not full, because node 4 has a left child (8) and no right child.
Running the four checks on this list prints (from_list builds the tree for the node-based checks):
[1, 2, 3, 4, 5, 6, 7, 8] full=False complete=True perfect=False list_complete=TrueExample 3: a question about leaves
A complete tree is stored in a list of 100 positions. How many leaves does it have, and where do they start?
Leaves are the positions from n // 2 to n - 1. Here n // 2 is 50, so the leaves are indices 50 to 99, which is 50 leaves. The internal nodes are indices 0 to 49, which is also 50 nodes. The height is (100).bit_length() - 1, which is 6. A check of the leaf rule for every size from 1 to 20 found no failures.
Common mistakes
Adding a None to a queue and reading it later
A deque accepts None, so the add itself never fails. The failure comes later, when the walk takes the None out and reads an attribute of it. The complete-tree test avoids this by checking if node is None right after popleft(), before it reads node.left or node.right. The code below leaves out that check. It is shown without the run mark because it stops with an error.
from collections import deque
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_complete_no_check(root):
queue = deque([root])
while queue:
node = queue.popleft()
queue.append(node.left)
queue.append(node.right)
return True
is_complete_no_check(TreeNode(1))The output is:
Traceback (most recent call last):
File "main.py", line 20, in <module>
is_complete_no_check(TreeNode(1))
~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^
File "main.py", line 15, in is_complete_no_check
queue.append(node.left)
^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'The first node is the root, which works. Its children are None, and the next time the walk takes one out, node.left fails. The fix is the None check after the popleft() call.
Walking up past the root
parent(0) returns -1 in Python, not 0. A loop that walks up from a node to the root and calls parent on each index must stop at index 0. If the loop does not stop, it reaches -1, and then values[-1] reads the last item of the list without any error, because Python counts negative indexes from the end. The result is a wrong answer with no message. Stop the walk when i == 0.
Using a shift with the wrong exponent
A common mistake is to write (1 << h) - 1 for the number of nodes in a perfect tree. That is one level too few. For height 2, the formula must give 7 nodes. (1 << 2) - 1 gives 3, which is the count for height 1. Use (1 << (h + 1)) - 1.
Mixing up the height of an empty tree
Some textbooks say an empty tree has height 0, and some say -1. The formulas in this lesson need -1, so that a single node has height 0. If your code returns 0 for an empty tree but keeps the formula (1 << (h + 1)) - 1, a single node has height 1, and the perfect test says it is not perfect. Pick one convention and use it in every function.
Practice
Exercise 1
Classify the tree [1, 2, 3, 4, None, 5, 6] as full, complete or perfect. Use the list form. Answer each question yes or no.
Show the answer
No, no and no. Node 2 has only a left child, so the tree is not full. Index 4 is None before index 5, so the tree is not complete. Seven positions are needed for a perfect tree of height 2, and there are only six nodes, so it is not perfect.
Exercise 2
How many nodes does a perfect tree of height 4 have? How many does a complete tree of height 3 have, at least and at most?
Show the answer
A perfect tree of height 4 has 2^5 - 1, which is 31 nodes. A complete tree of height 3 has at least 2^3, which is 8 nodes, and at most 2^4 - 1, which is 15 nodes.
Exercise 3
A complete tree is stored in a list of length 10. What are the indices of the children of index 3? What is the parent of index 9? Which indices are leaves?
Show the answer
The children of index 3 are at indices 7 and 8. The parent of index 9 is index 4, because (9 - 1) // 2 is 4. The leaves start at 10 // 2, which is index 5, so the leaves are indices 5 to 9.
Exercise 4
Predict the output of is_complete_list for [1, 2, None, 4]. Then say why.
Show the answer
The output is False. Index 2 is None, and index 3 holds 4, which comes after that gap. In the tree, node 1 has no right child, but node 2, on the left, has a child 4. The gap on level 1 comes before a real node, so the tree is not complete.
Exercise 5
A complete tree has 100 nodes. What is its height?
Show the answer
The height is 6. The formula (100).bit_length() - 1 gives 6, because 2 to the power 6 is 64, which is at most 100, and 2 to the power 7 is 128, which is more than 100.
Summary
- A full tree has no node with exactly one child. A complete tree fills each level from the left, with no gap before the last real node. A perfect tree is full and complete, and every leaf is on the same level.
- A perfect tree of height
hhas2^(h+1) - 1nodes. A complete tree withnnodes has a height of the base 2 logarithm ofn, rounded down. - In a list, the children of index
iare at2 * i + 1and2 * i + 2, and the parent of indexiis at(i - 1) // 2. - A complete tree in a list has no gaps. Check for a gap by looking for a
Nonefollowed by a real value. - Check for
Noneright after taking an item from a queue, and stop any walk up the tree at index 0.