Chapter 9: Trees

9.1The tree concept

Every structure so far has been linear: each element is followed by at most one other. An organization chart, a file system, or a family tree will not fit on a line, because an element can have several elements below it, each with its own below it. This section sets up the language of trees, the structure for such hierarchies.

9.1.1What is a tree?

A tree is a nonlinear structure that stores elements hierarchically. Each element is a node, and a line joining two nodes is an edge. The single node at the top is the root; computer scientists draw trees upside down, as in Figure 9.1.

Each edge joins an upper node, the parent, to a lower one, its child. One rule makes a tree a tree: every node except the root has exactly one parent, and the root has none. The number of children is unlimited — zero, one, or many.

The second condition rules out a cycle: you cannot leave a node, walk along edges without reusing one, and return. A cycle would force some node on it either to have two parents or to climb forever without reaching the root.

The most used numerical fact about trees concerns edges. Every non-root node is joined to its parent by exactly one edge, so pairing each edge with its lower end is a one-to-one correspondence.

Figure 9.1 agrees: seven nodes, six edges. The rule works both ways: the node count gives the edge count at once, and a connected structure with at least as many edges as nodes must contain a cycle.

9.1.2Hierarchies in everyday life

People drew hierarchies as trees long before computers.

• File system. The root directory (/ on Unix-like systems) is at the top. Folders hold folders and files; files hold nothing. Folders are internal nodes, files leaves.
• Book. Parts divide into chapters, chapters into sections; the table of contents is the tree written with indentation.
• Geography. Continents contain countries, countries provinces, provinces cities.
• Web page. <html> contains <head> and <body>, which contain further elements; the browser builds a tree of them, the Document Object Model (DOM).

Figure 9.2 also shows why a file has one full path: notes.txt is reached only along /home/ann/notes.txt. With one parent per node, the path down from the root is unique. Shortcut (link) files add extra connections, and the structure stops being a pure tree.

9.1.3When is a structure a tree?

Without a marked root there is no notion of parent, so for an arbitrary linked structure we restate the definition: the structure must be connected (a path joins every pair of nodes) and have no cycle. Then it has one edge fewer than nodes, and any node can be chosen as the root; each node's parent is then its unique neighbor toward the root.

We never checked for cycles; the count did it. Connecting n nodes takes at least n − 1 edges, and one more edge joins two nodes that already have a path between them, closing a cycle. So “connected with n − 1 edges” means “connected and acyclic.”

Figure 9.4 shows the three typical violations. The triangle has three edges for three nodes, one too many, so a cycle forms. In the middle, whatever the root, the bottom node is reached by two paths. On the right, three nodes share one edge; with an edge missing, the structure splits. A collection of disjoint trees like this is a forest.

9.1.4Root, internal nodes, and leaves

Whether a node has children matters in nearly every tree algorithm: a recursive method usually stops at a leaf and descends into the children of an internal node.

• Root: the top node, the one without a parent — the root directory of a file system.
• Internal node: a node with at least one child — a folder.
• Leaf: a node with no children, also called an external node — a file.

Figure 9.5 makes two subtle points. First, “root” and “internal node” overlap: the root is defined by position, internal nodes and leaves by their number of children. Second, leaves need not share a level: 9 is a child of the root and a leaf, like 4, 5, 6, and 7. In a one-node tree the root is a leaf.

9.1.5Relationships between nodes

The terminology comes from family trees. A node's parent is directly above it, its children directly below, and children of one parent are siblings. The nodes on the path up to the root are its ancestors; all nodes reachable going down are its descendants. Table 9.1 illustrates these on Figure 9.6.

Ancestor and descendant are inverses: M's ancestors are H, D, A, so M is a descendant of each. The root is everyone's ancestor, a leaf no one's. Some sources count a node as its own ancestor and descendant; here they exclude the node, so a node's descendants are the other nodes of its subtree.

Sharing a row does not make nodes siblings. In Figure 9.6, F's parent is B and G's is C, so they are cousins, not siblings; siblinghood means a shared parent.

Figure 9.7 shows the tree in four frames of the slide drawing that introduces the terms. Of its 13 nodes, A through M, seven are leaves (K, L, F, G, M, I, J) and six internal (A, B, C, D, E, H); 7 + 6 = 13, and by Theorem 9.1 there are 12 edges.

9.1.6Degree, depth, level, and height

Nearly every cost analysis on trees rests on a few measures of how much a node branches and how far it is from the root.

Depth looks up: how far below the root is this node? Height looks down: how long is the longest branch beneath it? The root has depth 0 and the tree's height; a leaf has height 0 and a depth that depends on where it sits.

These notes count edges. Some books count nodes and number levels from 1, so every depth and height comes out one larger. Both are consistent, but mixing them shifts results by one; check a source's convention before comparing.

Depth depends only on a node's ancestors, height on all its descendants. The code mirrors this: depth climbs the parent chain, height descends through the children.

9.1.7Paths and subtrees

Walking from node to node along edges traces a path, formally a sequence alternating nodes and edges:

p = (v₀, e₁, v₁, e₂, …, e_k, v_k)

Each edge e_i joins v_i−1 and v_i; the path has start(p) = v₀, end(p) = v_k, and length length(p) = k, its number of edges. A path repeating no node is a simple path. Depth and height are lengths of paths from the root down to a node and from a node down to its farthest leaf.

Figure 9.9 makes the proof concrete. K's ancestors are E, B, A and M's are H, D, A; the chains first meet at A, so the path climbs three edges and descends three, length 6, and no other path exists. “A file has exactly one full path” is a special case.

A subtree is a node together with all its descendants, a tree in its own right. The dashed frame in panel (d) of Figure 9.7 marks D's subtree: D, H, I, J, M. A folder with everything under it is a subtree, so copying or deleting a folder copies or deletes a subtree.

Subtrees make tree algorithms naturally recursive. A node's children are the roots of its subtrees, so a job on a tree can usually be phrased as: do it on each subtree, combine the results, and account for the root. Height is the first example: one more than the largest subtree height.

9.1.8Basic kinds of trees

The definition puts no limit on children, but limiting or ordering them often helps. Table 9.4 lists the four kinds we meet in this course.

The kinds nest: every BST is a binary tree, every binary tree a k-ary tree with k = 2, every k-ary tree a general tree. More constraints mean less flexibility but easier work. A BST search descends into one child per node, left for a smaller key, right for a larger: finding 6 on the right of Figure 9.10 goes left from 8 and right from 3, two comparisons.

These notes concentrate on binary trees. Every general tree can be stored as a binary tree, as the section on representations shows. Insertion, deletion, and balancing in BSTs are a large topic of their own, mentioned here only by definition.

9.1.9The tree ADT

Before using a tree in code, we must decide which operations give access to it. As with stacks and queues, it pays to separate the operations from their implementation; the description of what a structure does is its abstract data type (ADT). The Java interface below is the tree ADT of Goodrich, Tamassia, and Goldwasser.

public interface Tree<E> extends Iterable<E> {
  Position<E> root();
  Position<E> parent(Position<E> p);
  Iterable<Position<E>> children(Position<E> p);
  int numChildren(Position<E> p);
  boolean isInternal(Position<E> p);  // has a child
  boolean isExternal(Position<E> p);  // leaf
  boolean isRoot(Position<E> p);      // no parent
  int size();
  boolean isEmpty();
  Iterable<Position<E>> positions(); // all positions
}
// Position<E>: E getElement();

The interface is built around positions. A Position<E> stands for a place in the tree and has one operation, getElement(), returning the element there. The user never sees, references, or modifies the node objects; all access goes through ADT methods on positions. Whether the tree is linked or stored in an array is hidden, so client code survives a change of implementation.

The methods fall into three groups.

• Navigation. root() returns the root's position (null if empty); parent(p) returns p's parent, or null at the root; children(p) yields the children in order, as an Iterable usable in a for-each loop; numChildren(p) is p's degree.
• Queries. isInternal(p), isExternal(p), and isRoot(p) report whether a position is internal, a leaf, or the root. The names follow the reference textbook.
• General methods. size() and isEmpty() report the node count and emptiness; positions() iterates over all positions and iterator() (from Iterable<E>) over all elements.

The binary tree ADT adds three methods: left(p) and right(p) return the children (or null), and sibling(p) the sibling.

On Figure 9.11: numChildren(p) returns 2; isInternal(p) is true, isExternal(p) and isRoot(p) false; root() gives A, parent(root()) is null, and size() is 7.

9.1.10Code trace: depth and height

With the ADT we can compute depth and height without knowing the implementation; both methods transcribe their definitions almost word for word.

int depth(Position<E> p) {
    if (isRoot(p)) return 0;
    return 1 + depth(parent(p));
}
int height(Position<E> p) {
    int h = 0;
    for (Position<E> c : children(p))
        h = Math.max(h, 1 + height(c));
    return h;
}

depth(p) follows the definition: 0 at the root, otherwise one more than the parent's depth. It climbs the parent chain one edge per call, so for depth d it is called d + 1 times: O(d + 1) time and at most d + 1 stack frames.

height(p) looks downward. Starting from h = 0, the loop raises h to 1 + height(c) for each child c; at a leaf the loop never runs and 0 is returned. The method is called once per node of p's subtree, and iterating over children costs their number, which sums to the edge count, so a subtree of n_p nodes takes O(n_p).

Let us trace depth(G) and then height(B) on Figure 9.11. Table 9.5 gives the call stack (bottom to top) and returned values.

The trace shows a symmetry. depth calls on the way up and computes on the way down: the root says 0, and each frame adds 1. height calls on the way down and computes on the way up: leaves say 0, and each internal node adds 1 to its children's maximum. height(B) was called four times, for exactly B's subtree (B, D, E, G); A, C, F were never touched.

A tree's height can be found with height(root()) in O(n), or as the largest depth, which climbs separately from every node at cost O(n + Σ d_p). In a chain the depths 0, 1, …, n − 1 sum to n(n − 1)/2, so that costs O(n²). Use the first method.

9.2Binary trees

In a general tree a node may have any number of children, so each node must keep a variable-length child list. Limiting nodes to two children simplifies both storage and algorithms, which is why binary trees are the most widely used kind; expression trees, binary search trees, heaps, and Huffman trees are all binary.

9.2.1Definition of a binary tree

In a binary tree every node has at most two children, but what really sets it apart is that the children are named: each is a left child or a right child. Even an only child is on one particular side, and the side matters.

The definition is recursive but not circular: the subtrees shrink at every step until we reach the empty tree, the base case. It also dictates how binary tree methods are written: return a value for the empty tree; otherwise apply the method to both subtrees and combine the results.

In both drawings of Figure 9.13, A has one child, B. As general trees they coincide; as binary trees one has an empty right subtree and the other an empty left one. The difference matters: in a BST left means smaller keys, and inorder traversal outputs B A for the left tree but A B for the right.

Nodes need not be spread evenly. In the left structure of Figure 9.14 every node has only a left child, and the tree has degenerated into a chain, a skewed tree. It is a valid binary tree but loses most of the advantages: four nodes in a chain have height 3, evenly arranged only 2. With a million nodes, the gap becomes about 20 versus a million.

9.2.2Full, complete, and perfect binary trees

Three names describe the shape of a binary tree. They sound alike, they are often confused, and not every source uses them the same way, so hold on to the precise definitions below.

The definitions look at different things. Full is a local condition on each node and ignores overall shape, so a full tree can be very lopsided: if the right child is always a leaf and the left one branches again, the tree is full yet nearly a chain. Complete is a condition on levels; it allows one node with a single child, in the right position just above the last level. Perfect is the strongest: the tree has every node its height allows.

To test completeness, number the nodes level by level, left to right: root 1, its children 2 and 3, then 4 to 7. A tree with n nodes is complete exactly when they fill 1 to n without gaps; if 10 is empty while 11 is used, it is not. This numbering also underlies the array representation.

A perfect tree is both full and complete. Full and complete are otherwise independent: trees exist that are full but not complete, complete but not full, and neither.

9.2.3Telling them apart on four trees

We apply the three definitions to the four trees of Figure 9.16.

Rows (a) and (b) prove that full and complete are independent. Compare (b) and (c): in both, 5 has one child, but on the left (10) the numbering continues without gaps, while on the right (11) it leaves 10 empty. One node on the wrong side makes the tree incomplete.

9.2.4Node count and height

With at most two children per node, each level holds at most twice as many nodes as the one above. Every relation between node count and height follows from this; Table 9.7 collects them, and the justifications follow.

A sum of consecutive powers of two is one less than the next power: 1 + 2 + 4 + 8 = 16 − 1. Only perfect trees reach the upper bound (15 nodes at height 3, 31 at height 4); chains reach the lower one (4 nodes at height 3).

That is why these relations matter. Searching for a key or inserting a node follows one path from the root toward a leaf, costing O(h). A balanced tree has h ≈ log₂ n, about 20 levels for a million nodes (2²⁰ ≈ 10⁶); a skewed tree has h = n − 1, as slow as a linked list. Balancing search trees closes this gap.

9.2.5Leaves and internal nodes in a full binary tree

A full binary tree always has exactly one more leaf than internal nodes; the 7-node perfect tree in Table 9.7 has 3 internal nodes and 4 leaves.

To see why, note that every full binary tree grows from a single node by one repeated operation: since a leaf cannot get a single child, it gets two at once. Figure 9.17 shows the growth.

So no full binary tree has an even number of nodes, 6 for instance, and the node count fixes the rest: l = (n + 1)/2 and i = (n − 1)/2. A full tree with 15 nodes has 8 leaves and 7 internal nodes.

Applications use this directly. In an expression tree with binary operators, operators are internal nodes and numbers leaves, so an expression always has one more number than operators: (3 + 4) × (5 − 2) has 3 operators and 4 numbers. In Huffman coding every internal node joins two subtrees, so k characters give k leaves and k − 1 internal nodes.

Counting edges proves this. With i₁ one-child and i₂ two-child nodes, there are n − 1 = l + i₁ + i₂ − 1 edges; since every edge leads down to a child, there are also i₁ + 2i₂. Equating them gives l = i₂ + 1; in a full tree i₁ = 0 and we recover the theorem.

9.3Representations

On paper a tree is nodes and lines; in memory it is either an array of consecutive cells or objects pointing to one another. The choice of representation decides how fast we reach parents and children, how much memory we use, and how easily the tree grows.

9.3.1Array representation

The level-by-level numbering gives a natural way to put a binary tree in an array: the root goes in the first cell, its children in the next two, the next level in the next four. A node's children and parent are then found from its index by simple arithmetic.

The 1-based formulas are simpler, so many books leave cell 0 empty. Why they work: the first node at depth d gets index 2^d, since the levels above hold 2^d − 1 nodes. If j nodes precede a node on its level, their 2j children precede its children on the next, which puts the left child of index i at 2i and the right child beside it. Integer division by 2 maps both 2i and 2i + 1 back to i.

The 0-based formulas shift indices by one: 0-based i is 1-based i + 1, whose left child 2i + 2 is 0-based 2i + 1; the others follow likewise.

In Figure 9.18, E is at index 5. Its children would be at 10 and 11, beyond the 9 nodes, so E is a leaf; its parent is at ⌊5 / 2⌋ = 2, B. Nodes carry no references: parent and child are implicit in the position, and each access is O(1) arithmetic.

Arrays suit complete binary trees best: their nodes fill indices 1 to n exactly, wasting no cells, which is why binary heaps almost always live in arrays. In other trees empty positions become empty cells; we compute the cost below.

9.3.2Code trace: index arithmetic and the path to the root

The code turns the 1-based formulas into three methods and prints every ancestor of a node up to the root.

int left(int i)    { return 2 * i; }
int right(int i)   { return 2 * i + 1; }
int parent(int i)  { return i / 2; }
void pathToRoot(char[] a, int i) {  // from i up to the root
  while (i >= 1) {
    System.out.print(a[i] + " ");
    i = parent(i);
  }
}

In parent, i / 2 is Java integer division, which rounds down: exactly ⌊i / 2⌋. pathToRoot(a, i) prints a[i] and moves i to the parent while i ≥ 1. The root's “parent” is ⌊1 / 2⌋ = 0, which stops the loop; that is why an empty cell 0 is handy, meaning “no parent.”

Two points stand out. First, a child index must be checked against the length: the left child exists if 2i ≤ n, the right if 2i + 1 ≤ n; otherwise the code reads past the end and throws ArrayIndexOutOfBoundsException. In an incomplete tree the cell may also be empty. Second, siblings share a parent: 8 and 9 both lead to 4, since integer division drops the right child's extra 1.

Each pass roughly halves the index, so the loop runs depth + 1 times, at most ⌊log₂ n⌋ + 1 in a complete tree: O(log n). This is also why heap operations are fast: moving an element up takes at most height-many steps, like this loop.

9.3.3Wasted space in the array

The array reserves a cell for every position, whatever the tree's shape: a node's index depends only on its position, so if the tree is not complete, the empty positions before it become empty cells.

In Figure 9.20 each node is the previous one's left child, so the index doubles: 1, 2, 4, 8, 16, and five nodes need 16 cells, 11 empty. A right-skewed chain is worse: with 2i + 1 the indices are 1, 3, 7, 15, 31.

In general n nodes may need up to 2ⁿ − 1 cells: a chain of height n − 1 forces room for every position of the perfect tree of that height. A right-skewed chain of 30 nodes needs over a billion cells. Such exponential waste makes arrays impractical for trees of unpredictable shape.

9.3.4Linked representation

Alternatively, each node is an object pointing to its children — the linked-list node adapted to trees, with two references, left and right, instead of one.

public class TreeNode {
    int data;
    TreeNode left;    // left child (null if none)
    TreeNode right;   // right child (null if none)

    public TreeNode(int data) {
        this.data = data;   // left = right = null
    }
}

data holds the node's value; left and right point to the children, or are null. The constructor sets only data; unassigned reference fields default to null, so a new node starts out as a leaf.

A small tree can be built by hand:

// build a small tree rooted at 9
TreeNode root = new TreeNode(9);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

This creates root 9, its children 2 and 3, and, through root.left.left, 4 as the left child of 2. Node 2 has no right child, and 3 has no children.

Memory goes only to existing nodes: however skewed the tree, n nodes are n objects. Adding a node means creating an object and pointing a reference at it, O(1) once the spot is known. The price is access: we must follow references from the root, with no jumping by index, and moving to a parent requires an extra parent field.

Count the references in Figure 9.22: seven nodes have 14 fields. Six are non-null, one per edge (Theorem 9.1), and 8 are null. This is no accident.

So more than half of a linked binary tree's reference fields are always empty: 51 of 100 in a 50-node tree. Threaded binary trees put this space to use, pointing empty left and right references to the previous and next node in inorder.

9.3.5Array or links?

The two representations complement each other, as Table 9.11 shows.

The third row is another advantage of arrays: level i starts at index 2ⁱ, so its kth node is at 2ⁱ + k − 1; in Figure 9.18, the 3rd node of level 2 is F, at 4 + 3 − 1 = 6. With links we must walk level by level.

The rule is short: arrays for trees that stay complete, links for unpredictable shapes. A heap stays complete through insertions and deletions, so it lives in an array; a BST takes whatever shape its keys give it, so it uses links.

9.3.6Representing general trees

With unlimited children, a fixed number of reference fields will not do. Two solutions are common.

// 1) List of children
class GeneralNode {
    int data;
    List<GeneralNode> children
        = new ArrayList<>();
}
// 2) First child – next sibling
class SiblingNode {
    int data;
    SiblingNode firstChild;
    SiblingNode nextSibling;
}

In the first (GeneralNode), each node keeps its children in a list that grows as needed, and a for-each over children mirrors the ADT's children(p). It is intuitive, but every node carries a list object.

In the second (SiblingNode), each node has two references: its first child (firstChild) and its next sibling (nextSibling). To visit a node's children, go down to the first and walk right along the siblings; the child list becomes a linked list spread over the nodes.

Call the first-child reference “left” and the next-sibling reference “right,” and any general tree becomes a binary tree. Rotated 45 degrees, the right half of Figure 9.23 is one: B is A's left child; E and C are B's children; D is C's right child, F is E's right child, G is D's left child. Binary tree algorithms thus extend to general trees, and a forest becomes one binary tree if its roots are treated as siblings.

Use the child list if a node's kth child is accessed often: children.get(k) is O(1), against k steps along the sibling chain. The sibling form uses a small fixed amount of memory per node and needs no list object.

9.4Tree traversals

An array or list has one natural order of visiting: front to back. A tree has none. At a node, do we process the node or its subtrees first? Which subtree first? Or do we go level by level? Each answer gives a traversal, and each traversal naturally solves a different problem.

9.4.1What is a traversal?

Traversals come in two families. Depth-first traversals follow a branch to its end before backing up to the next; the three members differ only in when the root is visited relative to its subtrees. The breadth-first traversal, level order, scans level by level: the root, its children, its grandchildren.

The depth-first traversals are named for where the root falls: before (pre), between (in), or after (post) its subtrees, the left subtree always preceding the right. They follow the recursive definition — act at the root, apply the same traversal to each subtree — so when working one out by hand, treat each subtree as a small tree of its own.

9.4.2Preorder traversal

A preorder traversal has three steps:

1. Visit the root.
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.

visit(root);
preorder(root.left);
preorder(root.right);

A node precedes all its descendants in the output. On Figure 9.24: visit 1; enter the left subtree and visit its root 2; visit 2's subtrees, 4 and 5. Then the right subtree: 3, 6, 7. Output: 1 2 4 5 3 6 7.

Preorder fits whenever a node must be handled before its children. Copying a tree is the clearest case: children cannot be attached before their parent's copy exists. Writing a tree to a file uses preorder too, so the reader meets each node after its parent and can rebuild the tree. A table of contents is a preorder traversal, and on expression trees preorder gives prefix notation, operators before operands.

9.4.3Inorder traversal

In an inorder traversal the root is visited between its subtrees:

1. Traverse the left subtree in inorder.
2. Visit the root.
3. Traverse the right subtree in inorder.

inorder(root.left);
visit(root);
inorder(root.right);

A node comes after its whole left subtree and before its right one, so the output starts not with the root but with the leftmost node. On Figure 9.24 we go from 1 to 2 to 4; 4's subtrees are empty, so 4 is visited, then 2, then 5. With the left subtree done, 1 is visited; in the right subtree we again go far left: 6, 3, 7. Output: 4 2 5 1 6 3 7.

Geometrically, inorder lists the nodes in their left-to-right order in the drawing, as if each were dropped straight down onto a line: 4, 2, 5, 1, 6, 3, 7 in Figure 9.24.

Its key use is in binary search trees. Smaller keys lie left of every node and larger ones right, so inorder outputs the keys in increasing order; conversely, a binary tree with sorted inorder output (and distinct keys) is a BST. On expression trees inorder gives infix notation, minus the parentheses.

9.4.4Postorder traversal

In a postorder traversal the root is visited after both subtrees are finished:

1. Traverse the left subtree in postorder.
2. Traverse the right subtree in postorder.
3. Visit the root.

postorder(root.left);
postorder(root.right);
visit(root);

Every node follows all its descendants, and the root comes last. On Figure 9.24: the leftmost leaf 4, then 5, then 2; the right subtree gives 6, 7, 3; the root 1 is last. Output: 4 5 2 6 7 3 1.

Postorder fits whenever a node's work depends on its children's results. Deleting a tree must remove children first, or the references to them are lost; likewise a nonempty folder cannot be deleted before its contents. A folder's total disk usage, a tree's node count, and its height are all computed in postorder. On expression trees postorder gives postfix notation, the order of evaluation.

A quick check relates the outputs: the root is first in preorder, last in postorder, and between its subtrees in inorder — in Table 9.12, 1 starts, ends, and splits the outputs. This observation also underlies rebuilding a tree from two traversals.

9.4.5Three traversals, one tour: the Euler tour

One picture unites the three depth-first traversals. Walk around the tree from the left of the root, keeping the edges at your left hand. This Euler tour passes every edge twice, down and up, and meets every node three times: on its left, below it, and on its right.

The pass at which we write a node picks the traversal.

• On its left, on first arrival: preorder, A B D E C.
• Below it, between its subtrees: inorder, D B E A C.
• On its right, after both subtrees: postorder, D E B C A.

At a leaf the three passes are consecutive, since its subtrees are empty, so leaves keep the same relative order in all three traversals (D, E, C); only internal nodes move. The three traversals are moments of one tour. The tour takes 2(n − 1) edge steps, O(n) — another reason all three are O(n).

Some jobs need all three passes. Writing an expression fully parenthesized opens “(” on entering a subtree, writes the operator below, and closes “)” on leaving.

9.4.6Level-order traversal

A level-order traversal scans each level left to right, top down — the tree version of breadth-first search (BFS) on graphs.

Level order ignores subtree structure: after 2 it moves to 2's sibling 3, not its child 4, and 2's children wait until level 1 is done. Recursion, which finishes one subtree before starting the next, cannot express this jumping back and forth.

The solution is a first-in, first-out queue. A visited node's children join the back of the queue, so earlier nodes' children come out earlier, and each level enters the queue before the next.

Level order suits jobs where levels mean something: printing level by level, per-level sums or maxima, the tree's width, or the leaf nearest the root. For that last job it is ideal: the first leaf to leave the queue is among the nearest, and the traversal can stop without visiting deeper nodes.

9.5Coding the traversals

Traversals are defined recursively, and their shortest code is recursive. Behind the recursion sits an invisible structure, the call stack: each call pushes a stack frame holding its parameters, local variables, and return point. We first trace the recursive traversals on the call stack, then replace it with an explicit Deque used as a stack, and finally code level order with a queue.

All code uses TreeNode from the linked representation. The recursive traces use the four-node tree rooted at 9: 9's children are 2 and 3, and 2's left child is 4 (height 2).

9.5.1Recursive preorder and the call stack

public void preorder(TreeNode root) {
  if (root == null) {
    return;
  }
  System.out.print(root.data + " ");
  preorder(root.left);
  preorder(root.right);
}

If root == null we are in an empty subtree and return at once: the base case. Otherwise the method prints the root (line 5), recurses on the left subtree (line 6), then on the right (line 7), and at the closing brace (line 8) its frame is popped.

A null base case keeps the code simple — leaves need no special case, since their two calls return at once — at the price of one call per null child. By Theorem 9.5 there are n + 1 of those, so 2n + 1 calls in all: 9 for our tree.

Note the stack depth. At steps 4 and 5 it peaks at four frames — 9, 2, 4, and 4's null child. Depth is set by the path to the deepest null child: h + 1 nodes plus one null call, at most h + 2 frames; here 2 + 2 = 4.

Time is O(n), one constant-work call per node and per null. Extra memory is the stack depth, O(h): O(log n) if balanced, O(n) if skewed.

9.5.2Recursive inorder

public void inorder(TreeNode root) {
  if (root == null) {
    return;
  }
  inorder(root.left);
  System.out.print(root.data + " ");
  inorder(root.right);
}

Only the print has moved, between the two calls. A call no longer prints on entry; it traverses its whole left subtree first and prints on line 6, after the left call returns.

The output is 4 2 9 3: 9 after its left subtree, before its right. 9's frame, created at step 1, waits on line 5 until step 11 to print. A frame on the stack marks unfinished work.

9.5.3Recursive postorder

public void postorder(TreeNode root) {
  if (root == null) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  System.out.print(root.data + " ");
}

Now the print follows both calls (lines 5 and 6), on line 7: a value is printed only after both subtrees are fully traversed.

The output is 4 2 3 9. Side by side, the three traces make and return the same calls in the same order — 9, 2, 4, null, null, … — and differ only in where the print falls. This is the Euler tour in code: entering a call is passing on the node's left, the gap between calls passing below, and leaving passing on its right.

9.5.4Preorder with a stack

The system's call stack is limited: with Java's defaults a StackOverflowError comes after a few thousand to a few tens of thousands of frames, so recursion crashes on a chain of hundreds of thousands of nodes. An explicit java.util.Deque stack does the same job in heap memory, filling up only when memory runs out.

public void preorderIterative(TreeNode root) {
  if (root == null) return;
  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.push(root);
  while (!stack.isEmpty()) {
    TreeNode temp = stack.pop();
    System.out.print(temp.data + " ");
    if (temp.right != null)
      stack.push(temp.right);  // right first
    if (temp.left != null)
      stack.push(temp.left);   // left on top
  }
}

Preorder is the easiest: a node precedes its children, so it can be printed as soon as it is popped. Each pass pops, prints, and pushes the children, right first, then left, so the left child sits on top of the LIFO stack and its whole subtree is done before the right child's turn.

The stack is the recursion's to-do list: after pass 2, [3, 5, 4] means “4's subtree, then 5's, then 3's,” information the recursive version kept in the lines where frames 2 and 9 waited.

Each node is pushed and popped once: n passes, O(n). The stack holds at most one waiting right sibling per level plus the top node, here at most 3 (after pass 2): O(h) extra memory.

9.5.5Inorder with a stack

In inorder a node cannot be printed when pushed, since its left subtree comes first; the stack holds nodes “to print later.” Two moves alternate: while temp is a node, push it and go left; when temp is null, the top node's left subtree is done, so pop it, print it, and go to its right subtree.

public void inorderIterative(TreeNode root) {
  if (root == null) return;
  Deque<TreeNode> stack = new ArrayDeque<>();
  TreeNode temp = root;
  while (!stack.isEmpty() || temp != null) {
    if (temp != null) {
      stack.push(temp);
      temp = temp.left;
    } else {
      temp = stack.pop();
      System.out.print(temp.data + " ");
      temp = temp.right;
    }
  }
}

The loop condition has two parts, !stack.isEmpty() || temp != null, because right after the root is printed the stack may be empty while temp points to the untraversed right subtree. The trace, on the tree where 1's children are 2 and 3, 2's are 4 and 5, and 3 has only a left child 6, includes this moment.

At the end of step 8 the stack is empty; with only !stack.isEmpty() the loop would stop and 3 and 6 would never print. temp != null catches the waiting right subtree. The loop ends only when both are exhausted, after step 12, with output 4 2 5 1 6 3.

Each node is pushed and popped once and each null child reached once: O(n). The stack holds the nodes on the path to temp with unfinished left subtrees, at most h + 1: O(h) extra memory.

9.5.6Postorder with a stack

Postorder is hardest: a node prints only when both subtrees are done. A node on top of the stack has finished its left subtree, but we cannot tell about the right, so the code looks with peek before popping.

public void postorderIterative(TreeNode root) {
  TreeNode current = root;
  Deque<TreeNode> stack = new ArrayDeque<>();
  while (current != null || !stack.isEmpty()) {
    if (current != null) {
      stack.push(current);
      current = current.left;
    } else {
      TreeNode temp = stack.peek().right;
      if (temp == null) {
        temp = stack.pop();
        System.out.print(temp.data + " ");
        while (!stack.isEmpty()
           && temp == stack.peek().right) {
          temp = stack.pop();
          System.out.print(temp.data + " ");
        }
      } else {
        current = temp;
      }
    }
  }
}

The logic has three parts.

• Going left. If current is not null, push it and go left, as in inorder.
• Entering the right subtree. Otherwise look at the top node's right child (stack.peek().right). If it exists, the node must wait: set current to it and enter that subtree.
• Printing and climbing. With no right child, the top node is finished: pop and print it. The inner while then looks up: if the printed node is the new top's right child, that parent is finished too and is popped and printed, and so on up the chain.

temp == stack.peek().right tests reference equality — the same object? — asking “are we returning from this parent's right subtree?” If so, the parent prints; if the printed node was a left child, the parent's right subtree is still ahead and the loop stops. The trace uses the tree where 1's children are 2 and 3, 2's are 4 and 5, and 3 has only a right child, 6.

The end of the trace shows the inner loop at work: printing 6 at step 15 completes 3 (6 is its right child) and then 1 (3 is its right child) — one leaf finishing a whole chain of parents. 3's missing left child is harmless: at step 12 current = 3.left is simply null.

The cost is O(n): each node is pushed and popped once, and every peek leads to a pop or a right subtree. The stack holds the current root-to-node path, at most h + 1 nodes. A shortcut exists: stack-based preorder with the pushes reversed (left, then right) outputs root, right, left, and reversing that with a second stack gives left, right, root — easy, but O(n) extra memory.

9.5.7Level order with a queue

public void levelOrder(TreeNode root) {
  if (root == null) return;
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  while (!queue.isEmpty()) {
    TreeNode temp = queue.poll();
    System.out.print(temp.data + " ");
    if (temp.left != null)
      queue.add(temp.left);
    if (temp.right != null)
      queue.add(temp.right);
  }
}

This mirrors stack-based preorder with three changes: a Queue (a LinkedList) replaces the stack, add (to the back) and poll (from the front) replace push and pop, and children are added in natural order, left first, since FIFO returns them in that order.

The trace uses the tree rooted at 4, with children 3 and 7; 3's children are 5 and 8, and 7 is a leaf.

Pass 2 is the essence of level order: 3's children go behind 7, which shares 3's level and is processed first. Preorder would give 4 3 5 8 7; level order gives 4 3 7 5 8.

Each node enters and leaves once: O(n). Memory, though, depends on the width w, the size of the most crowded level, since the queue spans at most two consecutive levels: O(w), here at most 3. A perfect tree's last level has about n/2 nodes, so level order needs O(n) there, while stack-based inorder needs O(log n).

9.6Applications of traversals

Traversals do more than print. Nearly every tree algorithm visits nodes in some order and does work at each visit; this section applies that pattern to real problems.

9.6.1Expression trees

An arithmetic expression is naturally a tree. In (3 + 4) × (5 − 2) the multiplication happens last, and each of its operands is a subexpression.

The tree needs no parentheses: addition and subtraction sit deeper, so they are computed first. Precedence and grouping are built into the shape, and the three depth-first traversals give three notations.

Prefix and postfix need no parentheses; the order of symbols alone fixes the expression. Unparenthesized inorder does not: 3 + 4 × 5 − 2 happens to equal 3 + 20 − 2 = 21 under the usual precedence, but it is not the tree's expression. Correct infix puts every internal node's subtree in parentheses — an Euler tour writing “(” on entry and “)” on exit.

9.6.2Code trace: evaluate()

Evaluation is postorder: an operator needs both operand values first. The code assumes an ExprNode class holding a number (value) at a leaf and an operator character (op) at an internal node.

int evaluate(ExprNode node) {
  if (node.left == null && node.right == null)
    return node.value;           // leaf: operand
  int a = evaluate(node.left);
  int b = evaluate(node.right);
  switch (node.op) {             // internal node: operator
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    default:  return a / b;
  }
}

A node with no children is an operand, and its number is returned: the base case. Otherwise the left subtree's value goes into a (line 4), the right's into b (line 5), and the switch applies the operator. Order matters for subtraction and division: in a - b, a is the left operand. An expression tree is full, so the one-child case never arises.

Values flow upward, and the operators apply in the order +, −, × — postorder, matching the postfix form 3 4 + 5 2 − ×. The stack-based postfix evaluator does the same work, with the call stack as its stack. Each node is processed once: O(n) time, O(h) extra memory.

9.6.3Finding the largest value

An unordered binary tree hides its maximum anywhere, so every node must be checked. Recursively, the largest value is the largest of the root's value and the maxima of the two subtrees.

public int findMax(TreeNode root) {
  if (root == null) {
    return Integer.MIN_VALUE;
  }
  int result = root.data;
  int left = findMax(root.left);
  int right = findMax(root.right);
  if (left > result)
    result = left;
  if (right > result)
    result = right;
  return result;
}

An empty tree has no largest value, but its return value must not distort the comparison. Integer.MIN_VALUE (−2³¹) never wins left > result, so empty subtrees have no effect. The body is postorder: subtree results first, then the root.

The table lists calls in the order they finish — 5, 8, 3, 7, 4, postorder. With one call per node and per null child, 11 calls in all, time is O(n). In a BST we would just go right from the root, O(h); an unordered tree forces a look at every node.

9.6.4Recursive tree functions

evaluate and findMax share a pattern: a base value for the empty tree, otherwise the subtrees' results combined with the root. The pattern computes many basic properties in a few lines.

int size(TreeNode node) {            // number of nodes
    if (node == null) return 0;
    return 1 + size(node.left) + size(node.right);
}

int height(TreeNode node) {          // number of edges
    if (node == null) return -1;     // empty tree: -1
    return 1 + Math.max(height(node.left),
                        height(node.right));
}

int countLeaves(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null && node.right == null) return 1;
    return countLeaves(node.left) + countLeaves(node.right);
}

• size(node) counts nodes: 0 for an empty tree, otherwise 1 for the root plus size(node.left) and size(node.right).
• height(node) measures edges, and its base case returns −1. Odd as it looks, this makes a leaf's height 1 + max(−1, −1) = 0; returning 0 would give leaves height 1, measuring nodes.
• countLeaves(node) has two base cases: 0 for an empty tree, 1 for a node with two null children. Any other node returns the sum of its subtrees' counts, not counting itself.

On the four-node tree rooted at 9 (children 2 and 3; 4 is 2's left child) they give size = 4, height = 2, and countLeaves = 2 (leaves 4 and 3). Each processes every node once: O(n) time, O(h) stack space.

9.6.5Code trace: size()

The trace shows values carried up from the subtrees. All recursive calls come from line 3; Java evaluates left to right, so size(node.left) runs before size(node.right).

Nine calls are made, for four nodes and five null children: 2n + 1 = 9. Each node returns its subtree's size — 1 for 4, 2 for 2, 1 for 3, 4 for 9 — so one postorder pass sizes every subtree. Stored in the nodes, these sizes answer questions like “what is the kth smallest key?” quickly.

9.6.6Code trace: height()

Here the left call comes from line 3 and the right from line 4, the two arguments of Math.max being on separate lines. Same tree.

The result is 2, the two edges of 9–2–4. The call structure equals that of size; only the combination changes, maximum instead of sum. That is the pattern's power: changing the base value and the combining operation yields node sums, minima, occurrence counts, and much more from one skeleton.

9.6.7Code trace: countLeaves()

countLeaves returns at a leaf without further calls, so the leaves' null children are never visited and the trace is shorter.

Only five calls are made — four nodes plus 2's empty right child — against nine for size, because the leaf check stops descent at leaves. That check is also essential: without it the method returns 0 at empty trees and never produces a 1, so every tree would have 0 leaves. A leaf is what we count, so it needs its own base case.

9.6.8Rebuilding a tree from its traversals

One traversal does not determine a tree: preorder 1 2 fits 2 as either child of 1. Two suitable traversals together, with distinct values, determine it uniquely.

The method follows from the definitions. The first preorder element is the root; in the inorder output, the elements to its left form the left subtree and those to its right the right subtree. The left subtree's size then tells which preorder elements belong to it, and the step recurses on both subtrees. With postorder, the root is the last element instead.

Preorder plus postorder fixes the root but cannot separate the subtrees: A B and B A fit B as A's left or right child. Only inorder distinguishes them, writing a left child before the root and a right child after. In full trees there are no one-child nodes, so the ambiguity vanishes.

int p = 0; // next root in pre[]
TreeNode build(int[] pre, int[] in, int lo, int hi) {
    if (lo > hi) return null;         // empty range
    TreeNode node = new TreeNode(pre[p++]);
    int m = lo; while (in[m] != node.data) m++;
    node.left = build(pre, in, lo, m - 1);  // left part
    node.right = build(pre, in, m + 1, hi); // right part
    return node;
}

build(pre, in, lo, hi) builds the subtree for in[lo..hi] and returns its root, or null for an empty range (lo > hi). Otherwise pre[p] is the subtree's root: a node is created and p incremented. As a field, p is shared by all calls and sweeps the preorder array once. The root's index m in the inorder range splits it into in[lo..m−1] (left) and in[m+1..hi] (right). The left subtree must be built first, since its elements precede the right's in preorder.

The linear search for m, one per node over its range, sets the cost: O(n log n) for a balanced tree, whose ranges halve per level, and O(n²) for a skewed one, whose ranges shrink by one. Storing each inorder value's index in a HashMap beforehand finds m in O(1), bringing the build down to O(n).

9.6.9The cost of traversals

Every traversal visits each node once with constant work, so all take O(n) time. They differ in extra memory.

Depth-first memory follows height: small for a balanced tree (h ≈ log₂ n), O(n) for a skewed one (h = n − 1), where recursion may hit the stack limit and throw StackOverflowError while the stack-based version, using heap memory, keeps going.

Level-order memory follows width. A perfect tree's last level of about n/2 nodes costs the queue O(n); a skewed tree never queues more than one or two. So the families are opposites: level order is frugal on deep, narrow trees, depth-first on wide, shallow ones — on a perfect tree, O(n) versus O(log n) for recursive inorder.

9.7Common mistakes

Most tree bugs fall into a few types. The table gathers the mistakes discussed throughout; use it as a checklist when reviewing tree code.

These mistakes share a common root: failing to mirror the tree's recursive structure in the code. A tree is either empty or a root with two subtrees, and a correct tree method handles both cases explicitly — returning a meaningful value for the empty tree, and for a nonempty one combining the subtrees' results with attention to where the root goes. That last point is also the only difference among the traversals: does the root come before, between, or after its subtrees?

9.8Summary

• A tree is a hierarchical structure of nodes and of edges joining them in parent–child relationships. There is a single root, and every other node has exactly one parent. Hence there are no cycles, a tree of n nodes has n − 1 edges, and there is exactly one path between any two nodes.
• An internal node has at least one child; a leaf has none. Parent, child, sibling, ancestor, and descendant are used as in a family tree; being on the same level does not make two nodes siblings.
• Degree is the number of children. Depth is the number of edges from the root to a node, height the number from a node to its farthest leaf. The height of a tree is that of its root, the largest depth. Sources that count nodes give every value one larger.
• In a binary tree every node has at most two children, and left is distinguished from right. Full: 0 or 2 children at every node. Complete: all levels but the last filled, the last filling from the left. Perfect: all leaves at the same depth; both full and complete.
• A binary tree has at most 2^d nodes at depth d and at most 2^h+1 − 1 nodes for height h; ⌊log₂ n⌋ ≤ h ≤ n − 1. A full binary tree has one more leaf than internal nodes.
• In the array representation, the 1-based index i has children 2i and 2i + 1 and parent ⌊i/2⌋; it is ideal for complete trees (heaps) and wastes up to 2ⁿ − 1 cells on skewed ones. In the linked representation every node carries left and right references, n + 1 of which are null. General trees are stored with child lists or in first-child – next-sibling form.
• Preorder visits root-left-right, inorder left-root-right, postorder left-right-root; all three are different moments of the same Euler tour. Level order scans the tree level by level with a queue.
• Recursive traversals use at most h + 2 frames on the call stack. The explicit-stack versions do the same work in heap memory: preorder pushes right before left; inorder goes left and prints as it pops; postorder uses peek to check whether the right subtree is finished.
• On an expression tree, preorder gives prefix, postorder postfix, and parenthesized inorder infix notation; the value is computed in postorder. size, height, countLeaves, and findMax follow one pattern: a base value for the empty tree, then a combination of the subtrees' results.
• Inorder together with preorder (or postorder) determines a binary tree with distinct values uniquely. All traversals take O(n) time; extra memory is O(h) for the depth-first traversals and O(w) for level order.

9.9Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• tree
• node
• edge
• root
• parent
• child
• sibling
• ancestor
• descendant
• leaf
• internal node
• degree
• depth
• level
• height
• path
• subtree
• cycle
• position
• abstract data type (ADT)
• binary tree
• full binary tree
• complete binary tree
• perfect binary tree
• binary search tree (BST)
• heap
• traversal
• preorder
• inorder
• postorder
• level-order
• breadth-first search (BFS)
• depth-first search (DFS)
• expression tree
• recursion
• base case
• call stack
• stack frame
• queue

9.10Test Yourself

1. In a general tree, A is the root; A's children are B and C, B's children are D, E, F, C's child is G, and G's children are H and I. Which nodes are leaves and which internal? What are the degree, the number of edges, and the height of the tree? What are the depth and height of G?

   Answer

   The leaves are D, E, F, H, I and the internal nodes A, B, C, G (5 + 4 = 9 nodes). B has the largest degree (3), so the degree of the tree is 3. There are 9 − 1 = 8 edges. The longest path is A→C→G→H, so the tree has height 3. G has depth 2 (A→C→G) and height 1 (G→H).

2. What are the smallest and largest possible numbers of nodes in a binary tree of height 5? What is the smallest possible height of a binary tree with 100 nodes?

   Answer

   At least h + 1 = 6 (a chain) and at most 2⁶ − 1 = 63 (a perfect tree). For 100 nodes, height 5 is not enough (at most 63 nodes) but 6 is (at most 127); the smallest height is ⌊log₂ 100⌋ = 6.

3. How many leaves and internal nodes does a full binary tree with 21 nodes have? Stored in the linked representation, how many null child references does it have?

   Answer

   From n = 2i + 1, i = 10 and l = i + 1 = 11. The number of null references is n + 1 = 22. Check: each leaf has two null references, 2 · 11 = 22, and since both children of every internal node are present, there are no others.

4. In the 0-based array representation, what are the indices of the parent and children of the node at index 9? At which index does the same node sit in a 1-based array, and what are the corresponding indices there?

   Answer

   0-based: parent ⌊(9 − 1)/2⌋ = 4, left child 2 · 9 + 1 = 19, right child 20. In a 1-based array the same node is at index 10: parent ⌊10/2⌋ = 5, children 20 and 21. Every 1-based index is exactly one more than its 0-based counterpart.

5. The root is 10; 10's children are 5 and 15; 5's children are 2 and 7; 7 has only a left child, 6; 15 has only a right child, 20. What are the preorder, inorder, postorder, and level-order outputs? Is this tree a binary search tree?

   Answer

   Preorder: 10 5 2 7 6 15 20. Inorder: 2 5 6 7 10 15 20. Postorder: 2 6 7 5 20 15 10. Level order: 10 5 15 2 7 20 6. The inorder output is in increasing order, so the tree is a binary search tree.

6. preorderIterative runs on the tree of the previous question. What is on the stack (bottom to top) at the end of each pass? What is the most elements the stack holds?

   Answer

   Initially [10]. Pop 10, push 15 and 5: [15, 5]. Pop 5, push 7 and 2: [15, 7, 2]. Pop 2: [15, 7]. Pop 7, push 6: [15, 6]. Pop 6: [15]. Pop 15, push 20: [20]. Pop 20: []. The stack holds at most 3 elements, and the output is in preorder.

7. Which operator is at the root of the tree for ((9 − 3) / (1 + 2)) × 4? What are its prefix and postfix forms, and what value does evaluate return?

   Answer

   The last operation performed is the multiplication, so the root is ×; the root of its left subtree is / and its right child is 4. Prefix: × / − 9 3 + 1 2 4. Postfix: 9 3 − 1 2 + / 4 ×. evaluate computes 9 − 3 = 6, then 1 + 2 = 3, 6 / 3 = 2, and finally 2 × 4 = 8, returning 8.

8. Which tree has inorder output 8 4 9 2 5 1 3 7 and postorder output 8 9 4 5 2 7 3 1? What is its preorder output?

   Answer

   The last element of the postorder output is the root: 1. In the inorder output, 1 has 8 4 9 2 5 on its left and 3 7 on its right. In the right subtree, the next-to-last postorder element, 3, is the root, with 7 to its right. In the left subtree the root is 2, with 8 4 9 on its left and 5 on its right. The root of 8 4 9 is 4, with 8 as left and 9 as right child. The tree is 1(2(4(8, 9), 5), 3(—, 7)). Preorder: 1 2 4 8 9 5 3 7.

9. How many different binary trees have preorder output A B and postorder output B A? What additional information determines the tree?

   Answer

   Two: B can be either the left or the right child of A, and both trees have the same preorder and postorder outputs. The inorder output tells them apart: B A if B is the left child, A B if it is the right. The ambiguity arises because A has only one child.

10. Suppose the base case of height is written return 0 instead of return -1. What does the method return for the four-node tree rooted at 9 (9's children are 2 and 3; 2's left child is 4)? For a leaf?

    Answer

    A leaf returns 1 + max(0, 0) = 1. Node 2 returns 1 + max(1, 0) = 2, node 3 returns 1, and the root 1 + max(2, 1) = 3. The method now measures height in nodes: every value is one more than under the edge-based definition (the correct answer is 2).

9.11Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 8: defines the general and binary tree ADTs through the position abstraction and gives linked and array implementations; covers traversals, the Euler tour, and expression trees with Java code close to that of these notes.
• D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed., 1997), Section 2.3: the classic treatment of tree traversal, covering nonrecursive traversal algorithms, threaded binary trees, and the representation of general trees by binary trees in detail.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), the section on representing rooted trees in Chapter 10 and Appendix B.5: the first-child – next-sibling representation and the definitions and counting results for trees, in a more formal style.

9.12References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
3. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997.
4. Oracle, Java SE 17 API Specification: documentation for java.util.Deque, java.util.ArrayDeque, java.util.Queue, and java.util.LinkedList.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 9 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.