15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A binary tree gives each node at most two children, so level l holds at most 2^l nodes and a tree of height h holds at most 2^(h + 1) - 1. Height counts edges, so one node has height 0. Trees are classed as full, complete, perfect or skewed by how those positions are filled.
| Max nodes at level l | 2^l, with the root at level 0 |
|---|---|
| Max nodes through height h | 2^(h + 1) - 1, height counted in edges |
| Full | Every node has zero or two children |
| Perfect | Every internal node has two children and all leaves share one depth |
| Complete | Every level is full except possibly the last, which fills left to right |
| Skewed | Every internal node has one child, so height is n - 1 |
A binary tree gives each node at most two child positions: a left position and a right position.
The lesson uses these conventions throughout:
0.We will use these classifications:
n nodes has height n - 1.The formulas follow from the child positions:
l: 2^lh: 2^(h + 1) - 1For tree terminology and basic analysis context, see the supplied references: Algorithms, 4th edition companion site and the course-outline reference.
Use this tree for the whole lesson:
1 A
2 / \
3 B C
4 / \ /
5 D E FIts level-order positions are:
| Level | Positions from left to right |
|---|---|
| 0 | A |
| 1 | B, C |
| 2 | D, E, F, empty |
Writing the visible positions in level order with a null marker for the unused final slot gives:
1[A, B, C, D, E, F, null]Start at the root.
At level 0, there is one possible position:
1level 0: [ A ]
2capacity: 2^0 = 1Each node can create at most two positions one level below it. The root can create at most two positions at level 1:
1level 1: [ B ] [ C ]
2capacity: 2^1 = 2Those two nodes can create at most four positions at level 2:
1level 2: [ D ] [ E ] [ F ] [ empty ]
2capacity: 2^2 = 4Trace the supplied tree one level at a time.
| State | What is placed or measured | Result |
|---|---|---|
| State 0 | Place A at level 0. | Capacity is 2^0 = 1. |
| State 1 | Place B and C at level 1. | Capacity is 2^1 = 2, so level 1 is full. |
| State 2 | Place D, E, and F at level 2. | Capacity is 2^2 = 4, so one position is unused. |
| State 3 | Follow longest root-to-leaf paths: A → B → D, A → B → E, and A → C → F. | Each has 2 edges. Height h = 2. Maximum capacity through this height is 2^3 - 1 = 7. |
| State 4 | Count and classify. | There are 6 nodes. The tree is complete, not full, and not perfect. |
The complete-tree decision depends on the order of positions at the final level:
1[D] [E] [F] [empty]The occupied positions come first. The gap is at the far right. The last level is filled left to right, so the tree is complete.
Check the other classifications:
C has exactly one child, F.Possible positions double from one level to the next.
At level 0, there is at most one position. Every node at that level can contribute at most two child positions to level 1. Every node at level 1 can again contribute at most two positions to level 2.
The following invariant holds:
At level
l, each node can contribute at most two child positions to levell + 1; therefore level capacity can at most double from one level to the next.
The level-capacity rule follows step by step:
1level 0 capacity = 1
2level 1 capacity = 1 × 2 = 2
3level 2 capacity = 2 × 2 = 4
4...
5level l capacity = 2^lTo get the maximum number of nodes through height h, include every level from 0 through h:
11 + 2 + 4 + ... + 2^h
2= 2^(h + 1) - 1For the example, height is 2, so the maximum possible number of nodes is:
12^(2 + 1) - 1
2= 2^3 - 1
3= 7The actual tree has only 6 nodes because its final rightmost position is unused.
During a left-to-right scan of level-order positions, another fact holds:
Once a null position has been seen, every later position must also be null.
If a non-null node appears after a null gap, the tree is not complete.
For example:
1[A, null, C]The right child C appears after the missing left-child position. That violates the rule.
For a nonempty tree, compute four results:
Use two views of the same tree:
null markers for the complete-tree gap rule.The level-order list must include positions through its final occupied position. For the worked example:
1[A, B, C, D, E, F, null]A leaf has height 0.
For any other node, find the heights of both subtrees and use the longer one:
1height(node) = 1 + max(height(node.left), height(node.right))To make this work for leaves, use an internal helper convention:
1height(null) = -1Then a leaf gets:
11 + max(-1, -1) = 0The helper value does not claim that an empty tree has edge height -1 as the lesson’s external result. The empty tree is returned separately.
Scan positions from left to right.
null, non-null nodes are allowed.null, only null values are allowed.Inspect each existing node:
Use the overall height h.
h.A full tree can have leaves at different depths, so fullness alone does not establish perfection.
The following procedures do not mutate the tree or the level-order list.
Node has fields left and right, each either another Node or null.root is either a Node or null.levelSlots is a level-order view of the same tree. It includes null markers for missing positions through the final occupied position.ClassifyTree returns an object with status, height, complete, full, and perfect.status is "empty" and height is "no edge-based height".101 function ClassifyTree(root, levelSlots) -> result
202 if root = null
303 return {
404 status: "empty",
505 height: "no edge-based height",
606 complete: undefined,
707 full: undefined,
808 perfect: undefined
909 }
1010
1111 h <- HeightEdges(root)
1212 complete <- IsComplete(levelSlots)
1313 full <- IsFull(root)
1414 perfect <- IsPerfect(root, 0, h)
1515
1616 return {
1717 status: "nonempty",
1818 height: h,
1919 complete: complete,
2020 full: full,
2121 perfect: perfect
2222 }
23
2423 function HeightEdges(node) -> integer
2524 if node = null
2625 return -1
2726
2827 leftHeight <- HeightEdges(node.left)
2928 rightHeight <- HeightEdges(node.right)
3029 return 1 + max(leftHeight, rightHeight)
31
3230 function IsComplete(levelSlots) -> boolean
3331 sawGap <- false
3432
3533 for position from 0 to length(levelSlots) - 1
3634 if levelSlots[position] = null
3735 sawGap <- true
3836 else if sawGap = true
3937 return false
4038
4139 return true
42
4340 function IsFull(node) -> boolean
4441 if node = null
4542 return true
4643
4744 if node.left = null and node.right = null
4845 return true
4946
5047 if node.left = null or node.right = null
5148 return false
5249
5350 return IsFull(node.left) and IsFull(node.right)
54
5551 function IsPerfect(node, depth, targetHeight) -> boolean
5652 if node.left = null and node.right = null
5753 return depth = targetHeight
5854
5955 if node.left = null or node.right = null
6056 return false
6157
6258 return IsPerfect(node.left, depth + 1, targetHeight)
6359 and IsPerfect(node.right, depth + 1, targetHeight)The direct formulas are separate constant-space calculations when l or h is already given:
1maximumAtLevel(l) = 2^l
2maximumThroughHeight(h) = 2^(h + 1) - 1Use the original tree and its level-order slots:
1root = A
2levelSlots = [A, B, C, D, E, F, null]ClassifyTreeroot is A, not null. Do not return the empty-tree result.HeightEdges(A).Follow the recursive calls down to null child links, then return upward.
HeightEdges returns -1 for every null child, then 0 for leaves D, E and F, 1 for B and C, and 2 for A, so the height is 2 edges.
Back at line 11:
1h = 2At line 12, call IsComplete(levelSlots).
Line 31 starts with:
1sawGap = falseExecute the loop at line 33.
position | levelSlots[position] | Line taken | sawGap after the step |
|---|---|---|---|
| 0 | A | Lines 34 and 36 are false. | false |
| 1 | B | Lines 34 and 36 are false. | false |
| 2 | C | Lines 34 and 36 are false. | false |
| 3 | D | Lines 34 and 36 are false. | false |
| 4 | E | Lines 34 and 36 are false. | false |
| 5 | F | Lines 34 and 36 are false. | false |
| 6 | null | Line 34 is true. Line 35 sets sawGap <- true. | true |
The loop ends. No non-null position appeared after the gap. Line 39 returns:
1complete = trueAt line 13, call IsFull(A).
1IsFull(A)A is not null.A is not a leaf.A has both children, so do not return false.IsFull(B) first.1IsFull(B)B is not null and not a leaf.B has both children.IsFull(D) and IsFull(E).D and E are leaves, so each returns true at line 45.Line 50 for B returns true.
Line 50 for A then evaluates IsFull(C).
1IsFull(C)C is not null.C is not a leaf because it has child F.C.right = null.Line 50 for A returns:
1true and false = falseBack at line 13:
1full = falseAt line 14, call:
1IsPerfect(A, 0, 2)A is not a leaf.A has both children.IsPerfect(B, 1, 2).For B:
B has two children.D at depth 2. It is a leaf.2 = 2, so D returns true.E at depth 2. It is also a leaf.2 = 2, so E returns true.B returns true.Check:
1IsPerfect(C, 1, 2)C is not a leaf.C.right = null.Lines 58–59 for A return:
1true and false = falseBack at line 14:
1perfect = falseLines 16–22 return:
1{
2 status: "nonempty",
3 height: 2,
4 complete: true,
5 full: false,
6 perfect: false
7}The returned values match the board analysis.
HeightEdges uses a structural argument.
Base case: If node is null, lines 24–25 return -1. A leaf receives -1 from both missing children and returns:
11 + max(-1, -1) = 0Every leaf has edge-based height 0.
Recursive case: Suppose the recursive calls at lines 27 and 28 correctly return the edge heights of the left and right subtrees. Any longest path starting at node must go through one of those subtrees. Line 29 adds one edge for the link from node to its chosen child and selects the longer subtree path. It returns the correct edge-based height for node.
Applying this argument from leaves upward proves that line 11 computes the correct height for the root.
IsComplete has a loop invariant:
Before each iteration, every position before
positionfollows the complete-tree gap rule: after the first null position, no non-null position has appeared.
Initialization: Before the loop, line 31 sets sawGap to false. No positions have been examined, so the rule holds.
Preservation: Consider one position.
Termination: If the loop reaches line 39, no non-null position appeared after a gap. The occupied positions are leftmost at the last level, so the tree is complete.
IsFull also uses a structural argument.
IsFull(root) returns true exactly for full trees.
IsPerfect checks both parts of the perfect-tree definition.
All internal nodes have two children and all leaves occur at the same depth exactly when IsPerfect returns true.
The algorithm does not infer any classification from node count alone.
Let n be the number of existing nodes, and let h be the edge-based height.
If l or h is already given as a small integer, these calculations perform a fixed amount of arithmetic:
12^l
22^(h + 1) - 1Under the course arithmetic model, this is:
1Time: O(1)
2Auxiliary space: O(1)IsComplete scans the level-order positions once.
For the example, it examines these seven positions:
1A, B, C, D, E, F, nullFor a general level-order representation, each position is examined once. Therefore:
1Time: O(n)
2Auxiliary space: O(1)The scan may return earlier when it finds a node after a gap, but the worst case examines all positions.
IsFull inspects each existing node at most once. IsPerfect also inspects each existing node at most once.
1Time: O(n)Neither procedure stores all nodes. Their recursive calls follow one current root-to-leaf path. That path has at most h + 1 nodes, so their auxiliary call-stack space is:
1Auxiliary space: O(h)ClassifyTree runs these checks one after another, not nested inside one another. The total remains:
1Time: O(n)
2Auxiliary space: O(h)The tree and the supplied level-order representation are inputs, so they are not counted as auxiliary space.
Incorrect formula:
1maximumThroughHeight(h) = 2^h - 1Smallest exposing input:
1h = 0Wrong result:
12^0 - 1 = 0A tree of height 0 can contain one root node.
Correction:
1maximumThroughHeight(h) = 2^(h + 1) - 1For h = 0:
12^(0 + 1) - 1 = 1Incorrect assumption:
1if IsFull(root) then perfect = trueExposing tree:
1 A
2 / \
3 B C
4 / \
5 D EEvery internal node has two children, so the tree is full.
Wrong result:
1perfect = trueThe leaves are at different depths:
1C is at depth 1
2D and E are at depth 2Correction: a perfect tree must be full and all leaves must have the same depth. IsPerfect checks leaf depth against targetHeight.
Incorrect complete-tree condition:
1if node has a right child, continue scanningExposing input:
1 A
2 \
3 CLevel-order positions:
1[A, null, C]Wrong result:
1complete = trueThe scan reaches null first, then sees C. That is an occupied position after a gap.
Correction: once line 35 sets sawGap <- true, line 36 must reject every later non-null position.
| Input | Expected result |
|---|---|
| Empty tree | Handle separately; no root and no positive-height path. |
A only | Height 0; full, perfect, and complete. |
A with left child B only | Complete; not full; not perfect. |
A with right child C only | Not complete; not full; not perfect. |
A with children B and C | Height 1; maximum capacity 2^(1 + 1) - 1 = 3. |
A skewed tree with n nodes | Height n - 1. |
Executable objective: Given a level-order array with null markers, classify the represented tree as complete or not complete and return its edge-based height.
The tests will check these contract requirements:
0.0.1class Node:
2 def __init__(self, value, left=None, right=None):
3 self.value, self.left, self.right = value, left, right
4
5def height_edges(node):
6 if node is None:
7 return -1 # helper value so a leaf gets 0
8 return 1 + max(height_edges(node.left), height_edges(node.right))
9
10def is_complete(slots):
11 saw_gap = False
12 for s in slots:
13 if s is None:
14 saw_gap = True
15 elif saw_gap: # a node after a gap
16 return False
17 return True
18
19def is_full(node):
20 if node is None or (node.left is None and node.right is None):
21 return True
22 if node.left is None or node.right is None:
23 return False
24 return is_full(node.left) and is_full(node.right)
25
26def is_perfect(node, depth, target):
27 if node.left is None and node.right is None:
28 return depth == target
29 if node.left is None or node.right is None:
30 return False
31 return is_perfect(node.left, depth + 1, target) and is_perfect(node.right, depth + 1, target)
32
33# A
34# / \
35# B C
36# / \ /
37# D E F
38root = Node("A", Node("B", Node("D"), Node("E")), Node("C", Node("F")))
39slots = ["A", "B", "C", "D", "E", "F", None]
40
41h = height_edges(root)
42print("height =", h)
43print("complete =", str(is_complete(slots)).lower())
44print("full =", str(is_full(root)).lower())
45print("perfect =", str(is_perfect(root, 0, h)).lower())
46print("max nodes =", 2 ** (h + 1) - 1)1public class Main {
2 static class Node {
3 String value;
4 Node left, right;
5 Node(String value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
6 Node(String value) { this(value, null, null); }
7 }
8
9 static int heightEdges(Node node) {
10 if (node == null) return -1; // helper value so a leaf gets 0
11 return 1 + Math.max(heightEdges(node.left), heightEdges(node.right));
12 }
13
14 static boolean isComplete(String[] slots) {
15 boolean sawGap = false;
16 for (String s : slots) {
17 if (s == null) sawGap = true;
18 else if (sawGap) return false; // a node after a gap
19 }
20 return true;
21 }
22
23 static boolean isFull(Node node) {
24 if (node == null || (node.left == null && node.right == null)) return true;
25 if (node.left == null || node.right == null) return false;
26 return isFull(node.left) && isFull(node.right);
27 }
28
29 static boolean isPerfect(Node node, int depth, int target) {
30 if (node.left == null && node.right == null) return depth == target;
31 if (node.left == null || node.right == null) return false;
32 return isPerfect(node.left, depth + 1, target) && isPerfect(node.right, depth + 1, target);
33 }
34
35 public static void main(String[] args) {
36 Node root = new Node("A",
37 new Node("B", new Node("D"), new Node("E")),
38 new Node("C", new Node("F"), null));
39 String[] slots = {"A", "B", "C", "D", "E", "F", null};
40
41 int h = heightEdges(root);
42 System.out.println("height = " + h);
43 System.out.println("complete = " + isComplete(slots));
44 System.out.println("full = " + isFull(root));
45 System.out.println("perfect = " + isPerfect(root, 0, h));
46 System.out.println("max nodes = " + ((1 << (h + 1)) - 1));
47 }
48}1#include <algorithm>
2#include <iostream>
3#include <string>
4#include <vector>
5using namespace std;
6
7struct Node {
8 string value;
9 Node *left, *right;
10 Node(string v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
11};
12
13int heightEdges(Node* node) {
14 if (!node) return -1; // helper value so a leaf gets 0
15 return 1 + max(heightEdges(node->left), heightEdges(node->right));
16}
17
18bool isComplete(const vector<string>& slots) { // "" marks a null slot
19 bool sawGap = false;
20 for (const string& s : slots) {
21 if (s.empty()) sawGap = true;
22 else if (sawGap) return false; // a node after a gap
23 }
24 return true;
25}
26
27bool isFull(Node* node) {
28 if (!node || (!node->left && !node->right)) return true;
29 if (!node->left || !node->right) return false;
30 return isFull(node->left) && isFull(node->right);
31}
32
33bool isPerfect(Node* node, int depth, int target) {
34 if (!node->left && !node->right) return depth == target;
35 if (!node->left || !node->right) return false;
36 return isPerfect(node->left, depth + 1, target) && isPerfect(node->right, depth + 1, target);
37}
38
39int main() {
40 Node d("D"), e("E"), f("F");
41 Node b("B", &d, &e), c("C", &f);
42 Node root("A", &b, &c);
43 vector<string> slots = {"A", "B", "C", "D", "E", "F", ""};
44
45 int h = heightEdges(&root);
46 cout << boolalpha;
47 cout << "height = " << h << endl;
48 cout << "complete = " << isComplete(slots) << endl;
49 cout << "full = " << isFull(&root) << endl;
50 cout << "perfect = " << isPerfect(&root, 0, h) << endl;
51 cout << "max nodes = " << ((1 << (h + 1)) - 1) << endl;
52}1class Node {
2 constructor(value, left = null, right = null) {
3 this.value = value;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function heightEdges(node) {
10 if (node === null) return -1; // helper value so a leaf gets 0
11 return 1 + Math.max(heightEdges(node.left), heightEdges(node.right));
12}
13
14function isComplete(slots) {
15 let sawGap = false;
16 for (const s of slots) {
17 if (s === null) sawGap = true;
18 else if (sawGap) return false; // a node after a gap
19 }
20 return true;
21}
22
23function isFull(node) {
24 if (node === null || (node.left === null && node.right === null)) return true;
25 if (node.left === null || node.right === null) return false;
26 return isFull(node.left) && isFull(node.right);
27}
28
29function isPerfect(node, depth, target) {
30 if (node.left === null && node.right === null) return depth === target;
31 if (node.left === null || node.right === null) return false;
32 return isPerfect(node.left, depth + 1, target) && isPerfect(node.right, depth + 1, target);
33}
34
35const root = new Node('A',
36 new Node('B', new Node('D'), new Node('E')),
37 new Node('C', new Node('F')));
38const slots = ['A', 'B', 'C', 'D', 'E', 'F', null];
39
40const h = heightEdges(root);
41console.log(`height = ${h}`);
42console.log(`complete = ${isComplete(slots)}`);
43console.log(`full = ${isFull(root)}`);
44console.log(`perfect = ${isPerfect(root, 0, h)}`);
45console.log(`max nodes = ${2 ** (h + 1) - 1}`);Full, complete and perfect. Full means no node has exactly one child. Complete fills every level but the last, from the left. Perfect is full with all leaves at one depth.
Each node has at most two children, a left and a right, and either may be empty. The names describe position only. They say nothing about whether values are ordered.
No. A full tree can have leaves at different depths. With root A, children B and C, and B having children D and E, every internal node has two children, but C is at depth 1 and D at depth 2.
Yes to both. A perfect tree is full by definition, and because every level is completely filled, the last level has no gap, so it is also complete.
A tree of height h holds at most 2^(h + 1) - 1 nodes, so n nodes need h of at least log2(n + 1) - 1. The tallest shape is a skewed tree with height n - 1.