Trees and binary trees
Definitions, properties, representations, and basic algorithms for trees and binary trees, with proofs, index formulas, and traversal code.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Trees and binary trees organize hierarchical data so that searching, insertion, deletion, and traversal are efficient. Engineers use them in compilers (syntax trees), databases and file systems (directory trees, B-trees), networking (routing tries), and compression (expression and decision trees).
Key ideas
- Node: A data item with zero or more child links in a tree.
- Edge: A connection between a parent and a child node. If u is parent of v, there is a directed edge u→v. In rooted trees, edges are naturally directed from parent to child.
- Root: The unique node with no parent.
- Parent / Child / Siblings: If there is an edge u→v, u is parent of v; v is child of u. Children of the same parent are siblings.
- Leaf (external node): A node with zero children.
- Internal node: A node with at least one child.
- Degree of a node: Number of children of the node.
- Degree of a tree: Maximum degree of any node in the tree.
- Depth (level) of a node: Number of edges on the path from the root to the node. The root has depth 0.
- Height of a node: Number of edges on the longest path from that node to a leaf. A leaf has height 0.
- Height of a tree: Height of the root. Convention used here: height is counted in edges; an empty tree has height −1.
- Binary tree: A rooted tree in which every node has at most two children, distinguished as left child and right child (order matters). A missing child is denoted null.
- Strict (proper) binary tree: A binary tree in which every internal node has exactly two children (0 or 2 children per node).
- Full (perfect) binary tree of height h: A binary tree where all leaves are at the same depth h and every internal node has exactly two children.
- Complete binary tree: A binary tree where all levels are completely filled except possibly the last, and the last level’s nodes are as far left as possible.
- Degenerate (pathological) tree: A tree where each parent has exactly one child; behaves like a linked list.
- Extended binary tree (binary tree with external nodes): A representation that adds explicit null (external) children to every leaf so every internal node has exactly two children; useful for proofs.
Representation of trees:
General tree representations:
- Parent array: An array P[1..n] where P[i] gives the index of node i’s parent (root has P[root] = 0 or −1). Space: O(n). Easy to find parent; expensive to iterate children without auxiliary child lists.
- Children lists (adjacency lists): For each node, maintain a list of its children. Efficient to traverse subtrees.
- Left-child right-sibling (LCRS) binary tree: Represent a general k-ary tree using a binary tree where each node stores pointers to its leftmost child and to its immediate right sibling. Traversal of siblings uses right links; traversal down uses left links.
Binary tree representations:
- Linked representation: Each node stores data and two pointers (left, right). Optional parent pointer.
- Array (sequential) representation for complete binary trees: Nodes are stored level-wise. Index formulas depend on base index:
- 0-based indexing: For node at index i, left child is at 2i+1, right child at 2i+2, parent at floor((i−1)/2).
- 1-based indexing: For node at index i, left child is at 2i, right child at 2i+1, parent at floor(i/2).
Fundamental properties (with statements and typical derivations):
- Maximum nodes at a given depth: In any binary tree, the maximum number of nodes at depth d is 2^d. Reason: Each node at depth d−1 can contribute at most two children.
- Maximum nodes in a binary tree of height h: With height counted in edges, the maximum number of nodes is 2^{h+1} − 1. Derivation: Sum from d=0 to h of 2^d = 2^{h+1} − 1 (geometric series), achieved by a full binary tree.
- Minimum possible height for n nodes: h_min = ceil(log2(n+1)) − 1. Reason: n ≤ 2^{h+1} − 1 ⇒ h ≥ log2(n+1) − 1.
- Relationship between leaves and internal nodes of degree 2 in a strict binary tree: If I is the number of internal nodes (with exactly 2 children) and L is the number of leaves, then L = I + 1. Proof sketch: In any non-empty binary tree, number of edges E = (total children) = 2I + 1·K where K is number of internal nodes with one child. In a strict binary tree K = 0. Also E = (total nodes) − 1 = (I + L) − 1. So (I + L) − 1 = 2I ⇒ L = I + 1.
- Null-pointer property: In any binary tree with n nodes (linked representation), the number of null child pointers equals n + 1. Proof idea via extended tree: Replace each null child with an external node; the resulting strict binary tree has 2n + 1 nodes (n internal + n+1 external leaves). Count child links: internal nodes contribute exactly 2n non-null links; in the original tree there are 2n total child pointers; of these, exactly (n + 1) are null.
- Average depth bounds: For an n-node binary tree, the minimum possible average depth over all shapes is Θ(log n), achieved by near-complete trees; the maximum is Θ(n) in degenerate shapes. Balancing strategies (in another topic: Heaps and balanced trees) control height to O(log n).
Traversal orders (definitions; detailed algorithms are in the separate topic “Binary tree traversals: recursive and non-recursive”):
- Preorder (NLR): Visit node, then left subtree, then right subtree.
- Inorder (LNR): Visit left subtree, then node, then right subtree.
- Postorder (LRN): Visit left subtree, then right subtree, then node.
- Level-order (breadth-first): Visit nodes level by level from the root, left to right within each level.
Binary Search Tree (BST) as a special binary tree (full details in “Binary search trees” topic):
- BST property: For any node with key k, all keys in its left subtree are < k, and all keys in its right subtree are > k (assuming distinct keys). Inorder traversal outputs keys in strictly increasing order.
What to draw and label (for exams):
- Binary tree shapes: Draw nodes as circles. Label root at top. Left child edges go down-left; right child edges go down-right. For strict vs non-strict, show a node with two children vs a node with one child and a null mark.
- Array representation diagram: Draw an array with indices (0..n−1 or 1..n). Show node keys in array cells. Draw arrows annotating i→2i+1 and i→2i+2 (or 2i, 2i+1) to show child indices. Indicate empty spots as “—” or “None”.
- LCRS representation: For a general tree, draw each node with two outgoing pointers: one labelled “left-child” to its first child, and another labelled “right-sibling” to the next sibling. Show a chain across siblings with right pointers.
Space/time notes (brief, since full analysis belongs to “Algorithm analysis”):
- Linked binary tree uses O(n) space for nodes plus O(n) for pointers. Traversals are O(n). Searching in BST: average O(log n), worst O(n) when degenerate (details in “Binary search trees”). Array representation allows O(1) child/parent index computation but may waste space for sparse trees.
Formulas
d: depth (dimensionless). Applies to any binary tree, depth counted in edges from root (root at depth 0).
max_nodes_with_height(h) = 2^(h+1) − 1h: tree height in edges (dimensionless). Achieved by a full (perfect) binary tree.min_height_for_n(n) = ceil(log2(n + 1)) − 1n: number of nodes (dimensionless). Gives the minimum possible height with n nodes.L = I + 1(strict binary trees) L: number of leaves; I: number of internal nodes (each with 2 children). Dimensionless counts. Holds only for strict (proper) binary trees.null_pointers(n) = n + 1n: number of nodes in a binary tree (dimensionless). In a linked representation with left and right child pointers.EPL = IPL + 2n(extended binary tree) EPL: sum of depths of external (null) nodes; IPL: sum of depths of internal nodes; n: number of internal nodes. Useful for average path-length proofs.left_child_index(i) = 2i + 1andright_child_index(i) = 2i + 2(0-based array) i: node index (dimensionless). For complete binary trees stored level-wise starting at index 0.left_child_index(i) = 2iandright_child_index(i) = 2i + 1(1-based array) i: node index (dimensionless). For complete binary trees stored level-wise starting at index 1.parent_index(i) = floor((i − 1)/2)(0-based) andparent_index(i) = floor(i/2)(1-based) i: node index (dimensionless). For nodes i > 0 (0-based) or i > 1 (1-based).
Syntax to remember (Python-style pseudocode for nodes):
class Node: def __init__(self, key, left=None, right=None): ...- Preorder:
visit(node); preorder(node.left); preorder(node.right) - Inorder:
inorder(node.left); visit(node); inorder(node.right) - Postorder:
postorder(node.left); postorder(node.right); visit(node) - Level-order with queue:
enqueue(root); while q: node=dequeue(); visit(node); enqueue(children) - LCRS node:
class GNode: def __init__(self, key, left_child=None, right_sibling=None): ...
Worked examples
Example 1 — Model theory answer: Prove L = I + 1 for strict binary trees and derive n = 2^{h+1} − 1 for perfect trees. Answer:
- Definitions: A strict (proper) binary tree is one in which each internal node has exactly two children. Let I be number of internal nodes, L be number of leaves, and n = I + L be total nodes.
- Claim 1: L = I + 1. Proof: Count edges in two ways. In any non-empty tree, number of edges E = n − 1. In a strict binary tree, each internal node has degree 2 toward children, so total child links = 2I. These links are exactly the edges. Hence 2I = E = (I + L) − 1 ⇒ L = I + 1. QED.
- Claim 2: For a perfect (full) binary tree of height h (edges), n = 2^{h+1} − 1. Proof: Level d has 2^d nodes (0 ≤ d ≤ h). Summing a geometric series, n = ∑_{d=0}^{h} 2^d = 2^{h+1} − 1. QED.
- Corollary: For perfect trees, I = 2^h − 1 and L = 2^h. From Claim 1 and total count.
Example 2 — Build a binary tree from level-order with N for nulls, and print traversals. Complete Python program:
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
# Build tree from space-separated level-order tokens; use 'N' for null
# Example input: 1 2 3 4 5 N 6 N N 7 N N N
def build_tree_from_level(tokens):
if not tokens or tokens[0] == 'N':
return None
it = iter(tokens)
root = Node(int(next(it)))
q = deque([root])
for left_tok, right_tok in zip(it, it):
node = q.popleft()
if left_tok != 'N':
node.left = Node(int(left_tok))
q.append(node.left)
if right_tok != 'N':
node.right = Node(int(right_tok))
q.append(node.right)
return root
def preorder(node, out):
if node is None:
return
out.append(str(node.key))
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(str(node.key))
inorder(node.right, out)
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(str(node.key))
def level_order(root):
if root is None:
return []
q = deque([root])
out = []
while q:
node = q.popleft()
out.append(str(node.key))
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return out
if __name__ == '__main__':
try:
tokens = input().strip().split()
except EOFError:
tokens = []
root = build_tree_from_level(tokens)
pre, ino, post = [], [], []
preorder(root, pre)
inorder(root, ino)
postorder(root, post)
print('Preorder:', ' '.join(pre))
print('Inorder:', ' '.join(ino))
print('Postorder:', ' '.join(post))
print('Level-order:', ' '.join(level_order(root)))
Sample input:
1 2 3 4 5 N 6 N N 7 N N N
Exact output:
Preorder: 1 2 4 5 7 3 6
Inorder: 4 2 7 5 1 3 6
Postorder: 4 7 5 2 6 3 1
Level-order: 1 2 3 4 5 6 7
Explanation: The tree built is level-wise: 1 at root; children 2,3; 2’s children 4,5; 3’s left is N and right is 6; 4’s children N,N; 5’s left 7 then right N, etc. Traversals follow definitions.
Example 3 — Convert a general tree to its left-child right-sibling (LCRS) binary representation and map to an array for a complete case. Problem: Given the following general tree (describe and draw): Root A has three children B, C, D. B has two children E, F. C has no children. D has one child G. Draw (i) the original general tree, (ii) the corresponding LCRS binary tree with left-child and right-sibling pointers, and (iii) the array indices if the LCRS binary tree happens to be complete up to some level (for illustration only). Model answer outline:
- Original general tree: Draw A at top; three downward edges to B, C, D (left to right). From B, draw edges down to E and F. From D, draw edge down to G. C has no children. Label nodes clearly.
- LCRS binary tree construction steps (describe what to draw):
- For each node, point its left-child pointer to its first (leftmost) child; point each child’s right-sibling pointer to its next sibling.
- Draw A with a left edge to B (its first child). Draw B with a right-sibling edge to C, and C with a right-sibling edge to D. B’s left-child points to E; E’s right-sibling points to F. D’s left-child points to G. Nodes C, F, G have left-child = null (no children), and D’s right-sibling = null (no next sibling). Indicate right-sibling edges horizontally with arrowheads; left-child edges vertically/down-left.
- Array mapping note: LCRS is not generally stored in a heap-like array unless it is complete as a binary tree. If we label nodes in level-order of the LCRS binary tree as A(0), B(1), C(2), D(3), E(4), F(5), G(6), then using 0-based formulas left=2i+1, right=2i+2 gives child indices. Note: In our example, A has no right child in the LCRS binary tree (its right pointer is null; C is B’s right sibling via a right link), so heap-style indices do not correspond to actual pointers. These heap formulas apply only if the LCRS binary tree itself is (nearly) complete; otherwise linked nodes are preferred.
Common mistakes
- Confusing strict vs complete vs perfect: Strict means each internal has 2 children; complete concerns filling order; perfect means all leaves at same depth and all internals have 2 children.
- Off-by-one in array indices: Using left=2i instead of 2i+1 for 0-based arrays, or forgetting that parent of i=0 is undefined.
- Forgetting that inorder has no special meaning in general trees (only defined for binary trees). Inorder relies on left vs right child order.
- Assuming BST properties for any binary tree: Only BSTs satisfy left<node<right for keys.
- Not counting null pointers: When asked to prove n+1 nulls, students count only existing children and miss the conceptual external nodes.
- Traversal output order: Swapping preorder and postorder steps or printing the node twice.
For your exam
- Short notes: Properties (max nodes per level; max nodes for given height; min height for n nodes; L = I + 1; null pointers = n + 1). State assumptions and give 2–4 line derivations.
- Representations: Parent array, children lists, LCRS; linked vs array representation for binary trees. Compare when each is suitable (complete tree → array; sparse tree → linked).
- Diagrams: Draw LCRS conversion step-by-step with labelled left-child and right-sibling pointers. Draw array representation with index mappings.
- Programs: Build a binary tree from level-order (with null markers) and print preorder/inorder/postorder/level-order. Ensure I/O format is exact and output is line-for-line correct.
- Proofs: Provide edge-counting proofs for L = I + 1 and for null_pointers = n + 1. Mention extended tree for clarity.
- Derived questions: Compute height, number of leaves, and whether array indices are valid for a given node; justify with formulas.
Quick check
- Define a complete binary tree and state the index formulas for left and right children in a 1-based array representation.
- In any strict binary tree with 25 internal nodes, how many leaves are there? What is the total number of nodes?
- A binary tree has height h = 4 (edges). What is the maximum number of nodes it can have? What is the minimum height for n = 100 nodes? Answers: (1) A binary tree where all levels are full except possibly the last, and the last level is filled from left to right; left child at 2i and right child at 2i+1. (2) Leaves L = I + 1 = 26; total nodes n = I + L = 51. (3) Max nodes = 2^(4+1) − 1 = 31; min height = ceil(log2(100+1)) − 1 = ceil(log2(101)) − 1 ≈ ceil(6.658) − 1 = 7 − 1 = 6.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?