Trees and Heaps

This lecture introduces the first non-linear abstract data type: the tree. We define the tree and its vocabulary (root, internal node, external node, ancestors, descendants, depth, height), specialize it to binary trees (full, complete), study traversals and reconstruction, and then build on the complete-binary-tree idea to get the heap — a binary tree whose operations (insert, remove-min or remove-max) each cost O(log n). The lecture closes with an exam-style heap problem and a quiz discussion of when the master method does and does not apply.

5.1 Trees: A Non-Linear ADT

5.1.1 What a Tree Is

A tree is an abstract data type (ADT) that stores its elements hierarchically. Where the ADTs we met earlier — vectors, linked lists, stacks, queues — keep their elements in a flat sequence, a tree arranges them in levels, one element above another, like a family tree or an org chart.

The professor's picture is the one to keep: an org chart. The CEO sits at the top, the managers report to the CEO, the engineers report to the managers. The chart itself carries meaning — nobody in it is "just next to" anybody else; each person is above or below the others. The tree vocabulary matches that picture exactly:

• A node — one element of the tree, the "person" in the chart — is the basic building block.
• The parent-child relationship — the "reports to" line — joins a node to the node one level above it and to the nodes one level below it.
• Every element in a tree has exactly one parent element and zero or more children elements. That "exactly one parent" rule is what keeps a tree a tree: it forbids the tangles of a general graph, where one node could report to several bosses at once.

The top element of the tree — the one node that has no parent — is called the root (the "CEO" of the chart). Because every other node has exactly one parent, there is exactly one root, and every node can be reached from it by following parent links upward, one step at a time.

All the special vocabulary that goes with trees — root, internal node, external node, ancestors, depth, height, descendants, degree — is covered in detail in Section 5.2, and the applications of trees are collected in Section 5.6. The point of this section is only the shape: elements on levels, joined by parent-child links.

5.1.2 Why a Tree Is Called Non-Linear

A tree is a non-linear ADT. The natural follow-up question is: why? What makes an ADT linear in the first place? The answer that settles both questions is about access.

In a linear ADT, the elements are arranged sequentially, one after another, and all the data elements sit at the same level. In a tree, the elements are stored at different levels, and they are accessed hierarchically — you reach a lower element by moving through its ancestors. That parent-child structure, plus the fact that elements live on different levels, is what makes the tree non-linear.

The two families differ on four points, and a side-by-side table keeps them straight:

The rule of thumb: if the only question about two elements is which comes first, a linear ADT is enough. The moment the question becomes "which one is above which," you need a tree.

Everyday example: a shopping list is linear — milk, eggs, bread, in any order you like. The structure of a university — faculties, departments, courses — is a tree: a course belongs to a department, a department belongs to a faculty. The list cannot say that; the tree can. The analogy breaks where the tree's "exactly one parent" rule bites: a course belongs to one department, not to two — a real university is sometimes messier than a tree.

Where does this matter in the field? Nearly every large software system organizes something as a tree: the folders on a disk, the structure of a web page, the way a compiler reads your program. Section 5.6 collects the full list. For now, hold on to the one property all those uses rely on: hierarchical access through ancestors, not sequential access along a single row.

5.2 Tree Terminology

5.2.1 Root, Internal Nodes, and External (Leaf) Nodes

Every tree is made of nodes with a parent-child relationship: each element has a parent and zero or more children. From that single rule come four definitions that everything else builds on:

• Root — the node without a parent. It is the top of the tree.
• Internal node — a node with at least one child.
• External node (also called a leaf node) — a node with no children. "External" and "leaf" are the same thing; the course uses both words, and books use both too.
• Levels — the rows of the tree; the root sits at the top, its children one level down, and so on.

The etymology helps: "internal" nodes are the ones inside the structure, with something below them; "external" nodes are the boundary of the structure, with nothing below them. A leaf of a plant has nothing growing under it — same idea.

Two things about these definitions tend to trip students up, so be careful:

1. The root is an internal node. The root is the exception to "each element has a parent" — it has no parent — but the internal-node definition never mentions parents. An internal node is a node with at least one child, and the root definitely has children. So the root is one of the internal nodes. This is a common source of confusion; the answer to "is the root an internal node?" is yes, always, as long as the tree has more than one node.

1. External nodes can sit at different levels. There is no rule that says all leaves are on the bottom row. You can have an external node here and an external node further down; a node without children is external no matter where it sits. (We lean on this again in Section 5.3.4, where it decides how to compute the height of a tree.)

5.2.2 A Worked Example Tree

The example tree used throughout this discussion lets you practice every term at once:

        A
      / | \
     B  C  D
    / \ / \
   E  F G  H
     /|\
    I J K

Here A is the root — no parent. B, C, D are its children, and A, B, C, F are the internal nodes (each has at least one child). D, E, G, H, I, J, K are external nodes — leaves, at different levels. Notice the level structure: the leaves do not all sit on the same row — E, G, H are one row up from I, J, K — and that is allowed, exactly as the second warning above said.

Ancestors. The ancestors of a node are its parent, grandparent, great-grandparent, and so on, all the way up to the root. The ancestors of node J are F, B, and A — that's it. No one else. Work it out: J's parent is F, F's parent is B, B's parent is A, and A has no parent, so the chain stops. G and H are not ancestors of J: they are on the same level, and ancestors are only the nodes above J on its own path to the root.

Descendants. The descendants of a node are its children, grandchildren, great-grandchildren, and so on, all the way down. The descendants of C are G and H; the descendants of A are every other node in the tree — B, E, J, and the rest. Again, the rule is symmetric to ancestors: C's subtree (itself plus its descendants) is exactly the part of the tree that hangs below C.

Degree. The degree of a node is the number of its children. The degree of A is 3, because A has exactly three children. That's all the word means: degree of a node = count of its children. E has degree 0 (no children), B has degree 2 (E and F), and so on. Nothing else is counted — siblings, parents, and the rest of the tree do not contribute.

One node alone is not a tree worth having. A tree is normally built starting from a single node — in the initial phase of construction there is only one node. But if there is only one piece of information to store, why would you reach for a tree at all? There is no need. A tree earns its value when there are many elements to organize hierarchically; a single-node tree has no purpose.

Practice on the example tree before moving on: the descendants of B are E, F, I, J, K; the ancestors of H are C and A; the degree of F is 3; the external nodes are D, E, G, H, I, J, K (seven of them, at three different levels); the internal nodes are A, B, C, F. If you can name all of these from the drawing, every term in this section is yours.

5.2.3 Depth of a Node

The depth of a node is the number of its ancestors. Depth belongs to a node, not to a tree — hold that thought, because height (Section 5.3) belongs to a tree, and mixing the two up is the most common error in this whole topic.

In the example tree above:

• Depth of node K: K's ancestors are F, B, A — three of them — so the depth of K is 3.
• Depth of node C: C's only ancestor is A — depth 1.
• Depth of the root A: no ancestors — depth 0.

As simple as that: count the ancestors, that is the depth. One more way to see it: the depth is also the number of edges you must climb from the node to reach the root — K to F is one edge, F to B is the second, B to A is the third.

Where does this matter in the field? Depth is the measure of "how deep is this item buried in the hierarchy": in a file system, the depth of a file is the number of folder levels above it; in a chess search, the depth of a position is how many moves you have looked ahead. Every algorithm that walks a hierarchy (Section 5.3) will be measured against the depth of the node it visits.

5.3 Depth and Height

5.3.1 The Recursive Way to Think About Depth

Let V be a node of a tree. The depth of V is the number of ancestors of V, excluding V itself — when we counted J earlier, we counted F, B, A, not J. From that definition we get two clean rules:

• If V is the root, the depth of V is 0.
• Otherwise, the depth of V is 1 plus the depth of the parent of V:

$$\text{depth}(V)=\{\begin{array}{ll}0& \text{if }V\text{ is the root}\\ 1+\text{depth}(\text{parent}(V))& \text{otherwise}\end{array}$$

Read the pieces one by one. $\text{depth}(V)$ is the depth of the node V; $\text{parent}(V)$ is the node directly above V — V's parent, which exists because the "otherwise" branch says V is not the root. The formula says: the depth of V is the depth of its parent, plus one for the extra edge V-to-parent. Check it on J: the depth of J is 1 plus the depth of its parent F. The depth of F is 2, so the depth of J is 3.

Why define depth this way — one plus the parent's depth — instead of just saying "count the ancestors"? Because this form makes the recursion concept work. The depth of a node is defined in terms of the depth of a smaller node, which lets a single short recursive function compute it. That recursion is the reason this formulation exists; without it, you would have to walk the whole ancestor chain by hand.

5.3.2 The Recursive Depth Algorithm

The recursive definition translates directly into an algorithm. Here is the version used in this discussion, where T is the tree and V is the node whose depth we want:

Algorithm depth(T, V):
    if T.is_root(V):
        return 0
    else:
        return 1 + depth(T, parent(V))

The idea: if V is the root, answer 0. Otherwise add 1 to the depth of V's parent, and let the function call itself on the parent until it reaches the root.

A full trace. Consider the level-numbered tree below. The numbering looks strange on purpose — nodes 1, 2, 3, 4, 5, 7, 14 — and there is a reason for it: the children of node i are stored at positions 2i and 2i + 1, so the numbering itself encodes the shape of the tree (this is the level numbering scheme studied in Section 5.10).

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

Note what the recursion did: it called the function one by one until it reached the root, then passed the results back down the chain. This is a classic example of an algorithm built on the recursion concept.

5.3.3 Time Complexity of the Depth Computation

How much time does this recursive depth algorithm take? This is a trap question, and the standard wrong answer is O(n) — where n is the number of nodes in the tree. Watch why that is wrong.

The recurrence for the work done is

$$T(\text{depth}(V))=1+T(\text{depth}(\text{parent}(V)))$$

which reads: the cost of computing the depth of V is one unit of work plus the cost of computing the depth of V's parent. Since the depth of the parent is essentially the same quantity as the depth of the node, the cost is basically "1 plus the depth of V" — the number of recursive calls is exactly the length of the ancestor chain from V to the root.

Unroll the recurrence to see it land. Write $d=\text{depth}(V)$. The first call costs 1 and leaves a problem of size $d-1$ (the parent's depth), the second costs 1 and leaves size $d-2$, and so on:

$$T(d)=1+T(d-1)=1+1+T(d-2)=\cdots =\underset{d+1\text{ terms}}{\underbrace{1+1+\cdots +1}}=d+1$$

So the running time is $O(d)=O(\text{depth of }V)$. The constant $d+1$ — not $n$ — is what the algorithm actually spends.

In the trace above, we never touched nodes 4, 5, or 2. We did not even touch half the nodes. So the cost is not O(n): it is O(depth of the node). In the worst case — when the tree is skewed, meaning all the nodes line up on one side like a chain — the ancestor chain runs through every node in the tree, and then the time complexity is O(n).

5.3.4 Height of a Tree

Height is for a tree, and only for a tree. The height of a tree is the maximum depth of any node in the tree:

$$\text{height}(T)=\underset{V\in T}{\max }\text{depth}(V)$$

You find the depth of every node, and the node with the maximum depth gives the height. In the example tree of Section 5.2.2, the deepest nodes are I, J, and K at depth 3, so the height of that tree is 3. In the level-numbered tree above, node 14 has the maximum depth (3), so that tree's height is also 3.

One refinement: the height is the maximum depth of an external node. The maximum depth is always attained by an external node — an internal node always has children one level below it, so it cannot be the deepest. But note the catch: external nodes can sit at different levels, so not every external node has the same depth. You cannot assume all leaves are equally deep; you must find the deepest one.

These definitions may differ slightly from other books you have read. Follow the ones here: depth is for a node, height is for a tree — depth is the number of ancestors of a node, height is the maximum depth of any node (equivalently, of any external node). There will not be any confusion if you stick with that.

The height algorithm takes the reverse strategy from the depth algorithm. For a node V considered as the root of its own subtree, the height of that subtree is 1 plus the maximum height of V's children:

Algorithm height(T, V):
    if T.is_external(V):
        return 0
    else:
        h = 0
        for each child W of V:
            h = max(h, 1 + height(T, W))
        return h

Verbally: check whether V is an external node; if so, return 0. Otherwise, for every child W of V, compute the maximum of height(T, W), add 1 for the edge down from V, and return that. Starting from the root, every time you come one level down the height goes up by 1, until you reach an external node and stop. Depth climbed from the node up to the root; height climbs from the root down to the deepest leaf — both approaches were shown so you can see they are two sides of the same recursion.

Because the height algorithm visits every node exactly once (each node is the "V" of one call, and each call does O(1) work plus its recursive calls), it runs in O(n) time for a tree of n nodes — unlike the O(n²) plan of calling the depth algorithm once per node.

Run the height algorithm once by hand on the example tree of Section 5.2.2 to see the climb. Start at the root A: A is internal, so the answer is 1 plus the maximum over its children B, C, D. Each child is a smaller version of the same question:

• B is internal (children E, F). height(B) = 1 + max(height(E), height(F)). E is external, so height(E) = 0; F is internal with children I, J, K, all external, so height(F) = 1 + max(0, 0, 0) = 1. So height(B) = 1 + max(0, 1) = 2.
• C is internal (children G, H), both external: height(C) = 1 + max(0, 0) = 1.
• D is external: height(D) = 0.

So height(A) = 1 + max(2, 1, 0) = 3 — the whole tree has height 3, matching the deepest leaves I, J, K at depth 3. Notice the direction: the values computed at the leaves return upward, one level at a time, until the root adds its final 1.

5.3.5 Depth and Height in Pictures

The distinction between depth and height is best seen level by level. In the level-numbered tree:

       1        depth 0, whole-tree height 3
      / \
     2   3      depth 1, height of the subtree rooted here is 2
    / \   \
   4   5   7    depth 2
          /
         14     depth 3  ← this is the height of the tree

Read the picture as a graph with two axes: the vertical axis is the level (depth), and each row lists the nodes sitting at that depth. At the root, the depth is 0 and the height of the tree is 3. One level down, the depth of that node is 1 (one ancestor) and the height of the sub-tree rooted there is 2 — never call it the "height of the node." Height always refers to a sub-tree (or the whole tree); depth always refers to a node. That one distinction — depth of a node versus height of a sub-tree — is where most mistakes happen, and it is worth drawing once for yourself.

5.4 Binary Trees: Full and Complete

5.4.1 What Makes a Tree Binary

A binary tree is a tree in which each node has at most 2 children. The two words that carry the whole definition are "at most." The definition does not say every node must have two children — a node may have 2, 1, or 0 children. A tree where some node has only a single child is still a binary tree. Many students answer this wrong in quizzes and exams, because they read "binary" as "exactly two." It is at most two.

Why does the word carry such an easy trap? Because in everyday speech "binary" suggests two of everything — binary numbers, binary decisions. The technical definition only limits the maximum: two children per node is a ceiling, not a quota. A node with one child, or with none, is perfectly legal; what is illegal is a third child.

The binary tree is the most studied tree in computing, for one practical reason: the two-child limit is what lets a node's children be found by simple arithmetic (Section 5.10) and what keeps search and heap operations down to O(log n) — a node with an unbounded number of children would break both.

5.4.2 Full Binary Trees

A full binary tree is a tree in which every node other than the leaves has 2 children. Every internal node has exactly two children; every leaf has none. In the example below, the leaves are the four bottom nodes, and every node above them — the four internal nodes — has exactly two children:

        o
      /   \
     o     o
    / \   / \
   o   o o   o

That is a full binary tree. Check the count: 7 nodes, of which 4 are leaves and 3 are internal. Every internal node has exactly two children; no node has one child. "Full" is the name for the quota being met everywhere.

5.4.3 Complete Binary Trees

A complete binary tree is a full binary tree with one extra constraint on where the leaves sit:

1. Every node other than the leaves has 2 children (the full condition), and
2. All the levels except the last are completely filled, and
3. All the nodes at the last level are as left as possible.

"As left as possible" means the last row fills up from the left without gaps: you cannot give a node children until the nodes to its left — and the nodes one level up — already have their children. In the incomplete picture below, the two bottom-right nodes cannot have children, because the two nodes immediately to their left do not yet have children:

        o
      /   \
     o     o
    / \   /
   o   o o     ← the rightmost node on level 2 cannot
                get children until the node left of it does

Why insist on completeness at all? Because a complete tree has no gaps — when you number its nodes level by level (Section 5.10), the numbers are exactly 1, 2, 3, …, n with nothing skipped, which lets the whole tree live in one compact array. That is the property the heap depends on (Section 5.11).

So: every complete binary tree is a full binary tree, but not every full binary tree is complete. Full asks only about two-children-per-internal-node; complete adds "and pack the last level to the left." Be very clear about the two definitions — they are a favorite spot for exam questions.

The two definitions differ on exactly one axis, and the table shows it:

When to pick which way of speaking: say "full" when you only care about the two-children rule; say "complete" when the tree must also pack into a gapless array. Every complete tree is full; most full trees are not complete.

5.5 The Tree ADT and Position Abstraction

5.5.1 The Position ADT

To turn the tree concept into an ADT, we first need a way to talk about "a place in the tree" without exposing the raw node. That is the job of the position ADT: a position abstracts the node — it is a handle to a node, and users of the tree manipulate positions rather than nodes directly.

The position ADT has exactly one method: element(), which returns the element stored at that position. That is the whole position ADT. We never give outside code direct access to a node; everything is mediated through positions, which is precisely the point of defining a tree as an ADT.

Why hide the node? Think of the position as the seat number at a stadium and the node as the concrete slab under the seat. The seat number tells you where the person is sitting, and that is all the organizers need; nobody outside the stadium staff is allowed to rebuild the slab. A position gives the caller a stable "where" — even if the tree is reorganized underneath, the caller keeps talking to the same place through the same handle.

5.5.2 Methods of the Tree ADT

The tree ADT groups its operations into a few families. These are the generic methods:

• size() — number of elements in the tree.
• isEmpty() — boolean; true if the tree has no elements.
• elements() — returns an element iterator: a cursor that moves through all the elements (the actual values) of the tree, one after another.
• positions() — returns a position iterator: a cursor that moves through all the positions of the tree.

Positions and elements are different things. The positions iterator walks the places; the elements iterator walks the values stored in those places. Both are iterators, so both let you step through everything in the tree.

The accessor methods answer structural questions:

• root() — the position of the root.
• parent(p) — the position of the parent of position p.
• children(p) — the positions of all children of p.

The query methods check properties of a node:

• isInternal(p) — is position p an internal node?
• isExternal(p) — is position p an external node?
• isRoot(p) — is position p the root?

The update methods change the tree:

• swapElements(p, q) — swap the elements stored at positions p and q.
• replaceElement(p, e) — store element e at position p, and return the element that was there before.

Every one of these takes positions as arguments. V and W in the method signatures are positions, not raw nodes. You implement these methods in whichever programming language you use in real life; the ADT definition only fixes what they mean. And because the ADT contract is open, you can add your own methods on top — that flexibility is one of the main benefits of defining a tree as an ADT.

5.5.3 Time Complexities of the Tree Methods

The time complexities of these methods depend on how the tree is stored. With the level-numbering storage (Section 5.10), you get the following:

The constants come from level numbering: if the children of node i live at 2i and 2i + 1, then the parent of the node at position i sits at $\lfloor i/2\rfloor$ — a single arithmetic step. So root and parent are O(1). To test whether a node is internal, check whether 2i or 2i + 1 is occupied — O(1). To test whether it is the root, check whether it has a parent (position $\lfloor i/2\rfloor$) — O(1). Swapping and replacing work on positions you already hold, so they are O(1). Only the two iterator methods are O(n), because they must visit every element or every position of the tree.

The one that trips students up is children(p). It is not O(n).

5.5.4 Student Questions and Answers

A good way to keep this straight: children(p) is the only method whose cost depends on the shape of the tree at p. In the worst case a single node could have many children — the cost follows that node, not the whole tree.

This is the heart of the position abstraction: the "links" are arithmetic, not memory addresses. A linked implementation exists too (Section 5.10.3) and keeps the same time complexities, but the ADT never forces either one on you.

5.6 Applications of Trees

5.6.1 Everyday and System Uses

Trees show up everywhere, and knowing the standard applications makes the ADT concrete. Real-world uses mentioned in this discussion:

• File systems — the folder structure of an operating system is a tree: folders contain files and subfolders. The root of the tree is the root directory; every file is reached by following a path of folders down from it. File storage and database tables also use trees. When you type C:\Users\Name\Documents\report.docx, you are spelling out a path through the file-system tree.
• Database indexing — databases keep their indexes in tree structures so lookups stay fast at scale. A table with millions of rows cannot be scanned one row at a time for every query; an index tree lets the database find a key by walking a few dozen nodes instead. (Search trees — a later topic — are the standard form.)
• HTML documents — the Document Object Model (DOM) of a web page is a tree — the HTML document is stored as a tree, which is exactly why people who work with HTML hear about the DOM tree. Every tag is a node; every nested tag is its child. When JavaScript changes "the third child of the body element," it is navigating that tree.
• Compilers — a syntax tree is built by the compiler as it parses your program; the structure of an expression is a tree. The expression (a + b) * c becomes a tree whose root is * and whose left subtree is the + node with a and b as leaves. Everything from the parse phase onward works on that tree.
• Text tools — auto character and spell checkers use tree structures. The dictionary of a spell checker is often stored as a tree of prefixes, so that checking a word walks the tree letter by letter and rejects the word the moment a prefix stops existing.
• Data compression — Huffman coding, used for data compression, builds a binary tree over the symbols to assign short codes to frequent ones. Frequent characters sit near the root and get few bits; rare ones sit deep and get many bits — a file shrinks because the short codes dominate.
• Programming languages — the set and map containers in C++ are implemented using tree concepts. When you store keys in a std::map, the standard library keeps them in a balanced binary search tree, so lookups, insertions, and deletions each cost O(log n).
• Search and pathfinding — the A-star (A*) algorithm, a pathfinding algorithm used in artificial intelligence, works over a tree. Binary space partitioning (BSP), covered below, is another.

5.6.2 Games and AI

• Chess programs — computer chess engines build a huge tree of possible moves and positions, then prune that tree at runtime using heuristics to reach an optimal move. The tree is the backend of the engine. Each node is a board position; each edge is a legal move; the engine searches this tree ahead of time and scores the positions it can see. (This is the game tree behind the minimax algorithm studied later in the course.)
• 3D graphics and binary space partitioning — binary space partitioning (BSP) is used in almost all 3D games. In a first-person shooter — Call of Duty, BGMI, and the whole genre where the player sees the action through the eyes of the lead character — the engine must decide the ordering of the objects from front to back with respect to the viewer, so it knows what is rendered near the screen and what is hidden behind. BSP is implemented with a tree as its basic data structure: the space is split in two by a plane, each half is split again, and the tree records which side of each plane an object is on, so the renderer can walk the tree in view order.

5.7 Tree Traversals

5.7.1 What Traversal Means

Traversing a tree means visiting all the nodes. That is the entire definition, and it decides the time complexity instantly: because a traversal must visit every node, every traversal is O(n). There is no need to study the time complexity of in-order, pre-order, and post-order separately — the moment the word traversal appears, the answer is O(n), since we have to visit all the nodes.

A visit means performing whatever action the application needs at that node — printing the value, counting it, adding it to a total. The traversal is just the discipline of doing that action for every node, exactly once, in some agreed order.

5.7.2 In, Pre, and Post Order

The names in-order, pre-order, and post-order describe where the root goes. That is the only thing they mean:

• Pre-order — root first, then left subtree, then right subtree: root, left, right.
• In-order — left subtree first, then root, then right subtree: left, root, right — the root is in the middle.
• Post-order — left subtree first, then right subtree, then root: left, right, root — the root is visited at the end.

Keep that one fact in mind — in, pre, and post are all with respect to the root — and you can never go wrong. Each subtree is itself a binary tree, so the same rule applies inside it: in pre-order, the subtree root is visited before the subtree's own children, and so on. The recursion applies the rule at every level, which is why the whole traversal comes out as one neat sequence.

The names tell the story: "pre" = the root goes before the subtrees, "post" = the root goes after the subtrees, "in" = the root sits in between them.

5.7.3 A Worked Pre-Order Walk

On the level-numbered tree from Section 5.3.2, let us walk pre-order by hand:

       1
      / \
     2   3
    / \
   4   5

The same tree in in-order gives 4, 2, 5, 1, 3, and in post-order gives 4, 5, 2, 3, 1. Walk in-order once to see the difference: start at 1 — but do not visit it yet, because the root goes between its subtrees. Descend left to 2; again wait. Descend left to 4; 4 has no left subtree, so visit it now — 4. Return to 2, visit it — 4, 2 — then go to its right child 5 and visit — 4, 2, 5. Return to 1, visit it — 4, 2, 5, 1 — then the right child 3 — 4, 2, 5, 1, 3. The result lists the nodes "left to right" across the drawing. Notice what did not change: in every traversal, the left subtree (4, 5) is fully visited before the right subtree (3) is even started.

5.7.4 Student Questions and Answers

The deletion question shows why traversal order matters in practice: the same action — "delete this node" — is only safe in one of the three orders. The children must exist when the parent is deleted; only post-order guarantees that.

Related practice: binary tree traversals are also how you produce and convert expression notations — the prefix expression, infix to prefix, prefix to postfix — those are things you covered in your earlier studies; refresh them. As homework, try computing all three traversals on a fresh tree on your own — this will be an exercise you can check.

5.8 Reconstructing a Binary Tree from Traversals

5.8.1 The Key Idea

Given two traversals of a binary tree, you can reconstruct the tree. The rule: to construct a binary tree you need the in-order traversal and one other traversal — either pre-order or post-order. In-order is compulsory, because it is the only traversal that tells you which nodes sit on the left of the root and which sit on the right. With in-order plus one other traversal you can rebuild the tree completely; given the same two traversals you can also recover the third traversal without drawing anything.

Why is in-order the irreplaceable one? In pre-order you only know "some node comes before its subtree," and in post-order only "some node comes after its subtree" — neither one separates the left subtree from the right subtree. In-order is the only traversal that puts every node between its left subtree and its right subtree, so it is the only one that hands you the left/right split on a plate.

There is one exception, covered in Section 5.8.4: if you know the tree is full, you can skip in-order.

5.8.2 The Step-by-Step Method

The method is fixed — do not go by intuition. Intuition is exactly how students get this wrong in exams. The steps:

1. The last node of the post-order traversal is the root (if you are given post-order; if given pre-order, the first node is the root). The root always appears at the end of post-order.
2. Find the root in the in-order traversal. Everything to the left of it in in-order belongs to the left subtree; everything to the right belongs to the right subtree.
3. Repeat the process on each subtree — the same two rules, restricted to the nodes of that subtree: among the subtree's nodes, the one appearing last in post-order is the subtree root; split the subtree's in-order nodes around it.

The whole method is just these two rules applied over and over. Each round peels off one root and splits the remaining nodes in two; the recursion ends when a subtree has one node or none.

5.8.3 A Worked Example

Suppose the traversals of a binary tree are given as:

• in-order: p, x, y, n, c, d, e
• post-order: p, y, x, d, c, e, n

        n
      /   \
   left    right
 (p,x,y)  (c,d,e)

        n
      /   \
     x    right
    / \   (c,d,e)
   p   y

        n
      /   \
     x     e
    / \   /
   p   y c-d

        n
      /   \
     x     e
    / \   /
   p   y c
          \
           d

5.8.4 The Full Binary Tree Shortcut

If you know the tree is a full binary tree, you do not need in-order at all: you can construct the tree from pre-order and post-order alone. Why does that work? In a full tree every internal node has two children, so the split between left and right subtrees is forced — there is never a one-child ambiguity. Try it on an example: take a small full binary tree, write down its pre-order and post-order, then rebuild it from those two lists. Nothing complicated — it is very simple and direct. The distinction that makes it work is exactly the full versus non-full distinction from Section 5.4.

5.8.5 Exam Notes

A second exam note concerns how these problems are worked at all.

5.9 Properties of Binary Trees

5.9.1 The Relationships

Let N be the number of nodes of a binary tree, E the number of external nodes, and I the number of internal nodes. Two relationships hold for any binary tree:

$$E=I+1$$

$$N=2E-1$$

Read the first one in words: the number of external nodes equals the number of internal nodes plus one — there is always one more leaf than non-leaf. Verify them on a tiny example: a tree with one internal node (the root) and two external children has I = 1, E = 2, N = 3. Then E = I + 1 gives 2 = 1 + 1, and N = 2E − 1 gives 3 = 2·2 − 1. Both check out.

Try a bigger one before trusting the pattern: the full binary tree of Section 5.4.2 (three internal nodes and four leaves) has I = 3, E = 4, N = 7. Then E = I + 1 gives 4 = 3 + 1 ✓, and N = 2E − 1 gives 7 = 2·4 − 1 ✓. Each new full tree you draw will land the same way — that is the point of a derived property.

Where do these come from? They are not magic; they are edge-counting in disguise. Every node except the root has exactly one parent, so a tree with N nodes has exactly N − 1 edges. Now count the same edges the other way, from parent to child: every internal node has exactly two children in a full binary tree, so the edges total $2I$. Putting the two counts together:

$$\begin{array}{rlrl}N-1& =2I& & \text{(each edge is counted once from the child side, once from the parent side)}\\ N& =2I+1& & \text{(add 1 to both sides)}\end{array}$$

Since every node is either internal or external, $N=I+E$. Substitute and solve:

$$\begin{array}{rlrl}I+E& =2I+1& & \text{(substitute }N=I+E\text{)}\\ E& =I+1& & \text{(subtract }I\text{ from both sides)}\end{array}$$

From $E=I+1$ back into $N=I+E$, we get $N=2E-1$, the second formula. (The formula $N=2E-1$ follows because every internal node contributes two edges to the leaves, plus one for the root — draw it and the algebra appears by itself.)

The textbook rectangles you sometimes see hanging under nodes — the violet placeholders drawn under leaf nodes in tree diagrams — are not real nodes; they are placeholders used to make the tree picture look uniform. Treat them as placeholders, nothing more. (The rectangle style comes from the Goodrich textbook; the lecture keeps them in its figures only so the diagrams match the book.)

5.9.2 Why Deduce, Not Memorize

You do not have to learn these properties by heart. If you know what a tree is, you can deduce every one of them: draw any tree, count its internal nodes and external nodes, and the formulas fall out. The whole list of properties is for reference; you should be able to make sense of each one. They come in handy when you are coding a tree or implementing one — knowing E = I + 1, for instance, tells you the number of null links or leaf slots you are working with.

The same habit — derive instead of memorize — is the exam mindset for this whole course. If a formula like E = I + 1 is ever in doubt, sketch a small tree, count, and the relationship re-derives itself in ten seconds.

5.10 Binary Tree ADT, Level Numbering, and Storage

5.10.1 The Extra Methods

The binary tree ADT has all the methods of the tree ADT, plus three that only make sense when every node has at most two children:

• leftChild(p) — the position of the left child of p.
• rightChild(p) — the position of the right child of p.
• sibling(p) — the position of the other child of p's parent — the sibling of p.

As with the tree ADT, the arguments and results are positions, and the time complexity is the thing that matters. Sibling is a small but telling example of the ADT philosophy: you do not know how the tree finds the sibling — the position arithmetic of the next subsection does it in O(1) — you only know that sibling(p) answers the question "who is my brother or sister?"

5.10.2 Level Numbering

The tree ADT's O(1) methods only exist because of a storage convention called level numbering. The rules:

• The root has position 1.
• If v is the left child of node u, then position(v) = 2 · position(u).
• If v is the right child of node u, then position(v) = 2 · position(u) + 1.

$$\text{position}(v)=\{\begin{array}{ll}1& \text{if }v\text{ is the root}\\ 2\cdot \text{position}(u)& \text{if }v\text{ is the left child of }u\\ 2\cdot \text{position}(u)+1& \text{if }v\text{ is the right child of }u\end{array}$$

Equivalently: children of the node at position i live at 2i and 2i + 1, and the parent of the node at position i lives at $\lfloor i/2\rfloor$. From now on, when you hear the words "level numbering," do not panic — it is exactly this: i, 2i, 2i + 1.

Watch the arithmetic on a tiny tree. The root is 1. Its left child is $2\cdot 1=2$, its right child $2\cdot 1+1=3$. The left child of node 2 is $2\cdot 2=4$, the right child is 5 — and the parent of node 5 is $\lfloor 5/2\rfloor =2$, the node we started from. Every move, up or down, is one arithmetic step.

Run the same arithmetic on the level-numbered tree of Section 5.3.2 to see it in a full picture:

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

Node 2's children are at $2\cdot 2=4$ and $2\cdot 2+1=5$ — and indeed nodes 4 and 5 sit below node 2. Node 7 is the right child of node 3 (since $2\cdot 3+1=7$), and node 14 is the left child of node 7 (since $2\cdot 7=14$). The reverse move: the parent of node 14 is $\lfloor 14/2\rfloor =7$, the parent of 7 is $\lfloor 7/2\rfloor =3$, and the parent of 3 is $\lfloor 3/2\rfloor =1$ — the whole ancestor chain from Section 5.3.2 was just three floor-divisions. Notice how the numbering "skips": node 3's left child would be 6, but node 6 does not exist in this tree, so the number 6 is simply not used — the gaps in the numbering are exactly the missing children.

Why bother with the arithmetic? To get the O(1) accessors: given a position, the parent is one floor-division away, and testing for children is two multiplications away. That is the entire reason a tree would be stored this way.

5.10.3 Vector Representation

With level numbering, a binary tree can be stored in an array — the vector representation. The element of the node at position i goes in slot i of the array.

One deliberate detail: position 0 is not occupied. The root sits at position 1, and slot 0 is wasted — one location of the array is deliberately left empty. Why? Because with the parent at i and children at 2i and 2i + 1, the index 0 breaks the arithmetic: 2·0 = 0 and 2·0 + 1 = 1 would make 0 its own parent and child, and everything goes wrong. There is no hard and fast rule that it must be 1 — the convention is the root at 1 — but if you start the numbering anywhere else, you must adjust the arithmetic consistently.

In this scheme, some array slots are simply unused: if a node at position 3 has no children, slots 6 and 7 do not exist in the tree, though the array may be long enough to hold them. That is the price of the O(1) accessors — a few empty slots. For a complete tree (Section 5.4.3) there are no interior gaps at all, which is why heaps — always complete — love this storage.

A linked-list representation of trees is possible as well, and the time complexities stay the same: positions and elements are O(n); every other method is O(1). Which representation you choose is a matter of the operations you need — see Section 5.10.4.

5.10.4 Choosing the Underlying Storage

Vectors, positions, linked lists — all of these are abstract. When you actually implement an ADT, you use an array or a linked list underneath, and that base data structure has its own time complexity, which carries over: an implementation built on a costly base structure is itself more costly. So the thought process has to run one way only: first decide which operations your application needs, then choose the data structure that performs those operations in the least time. Never decide the data structure first and then wait for the operations to fit. If insertion and deletion are the only operations your application performs, look for a structure where insertion is O(1) and deletion is O(1) — a stack, for example — rather than one optimized for something you never do.

Two habits keep this decision honest. First, read the definition of an operation carefully, not just its function name — in past questions (for example, on doubly linked lists), the definition of an operation differed from what the function name suggested, and the running time had to come from the definition. Second, remember the layer rule: the ADT says what an operation means, the base structure says what it costs, and you pick the base structure by what the application will actually ask for.

5.11 Heaps: Definition and Properties

5.11.1 The Heap Contract

A heap is a binary tree that stores a collection of keys at its nodes and satisfies two more properties on top of the binary-tree ones: a relational property and a structural property. This is the definition to hold in your head:

A heap is a binary tree that satisfies a relational property (heap order) and a structural property (completeness).

Two words carry the whole definition, and each one does a different job. The relational property fixes who may sit above whom — it decides the ordering of the keys. The structural property fixes where the nodes may sit — it decides the shape of the tree. You will see both names again in the insert and remove procedures (Sections 5.12 and 5.13), where one of the two is always at risk of being broken.

5.11.2 Total Order Relations

Both heap properties are defined under one standing assumption: that the keys satisfy a total order relation. This is a math concept you already know; it just never got a name. Whenever we compare two numbers, we are assuming these three rules:

• Reflexive: a number is less than or equal to itself — $k_1\le k_1$.
• Antisymmetric: if $k_1\le k_2$ and $k_2\le k_1$, then both are equal — $k_1=k_2$.
• Transitive: if $k_1\le k_2$ and $k_2\le k_3$, then $k_1\le k_3$.

We never talk about these explicitly, but every comparison operation on numbers runs under the assumption that the total order relation holds — always. Why name it here? Because the heap-order property is a statement about comparisons — "every child is at least its parent" — and that statement only has a clean meaning if comparisons behave: the order must be consistent (transitive), total (any two keys can be compared), and honest about ties (antisymmetric). A "sorted" arrangement is only possible on top of a total order.

5.11.3 The Relational (Heap-Order) Property

The relational property is also called the heap-order property: for every node V other than the root,

$$\text{key}(V)\ge \text{key}(\text{parent}(V))$$

That is, every child is greater than or equal to its parent. A binary tree satisfying this is a min heap — the parent is small, the children are large (or equal).

Flip it around — parent is big, children are small:

$$\text{key}(V)\le \text{key}(\text{parent}(V))$$

— and you have a max heap. Min and max are always with respect to the parents: if the parent is large and the children are small, it is a max heap; if the parent is small and the children are large, it is a min heap.

The formal way to say it: the keys encountered on a path from the root to an external node are in non-decreasing order for a min heap, and in non-increasing order for a max heap.

Min and max are mirror images of each other, and the table keeps the mirror straight:

The choice is only a matter of which inequality you write: multiply either inequality by −1 (or flip the comparison rule) and one heap becomes the other. No separate theory is needed — everything in Sections 5.12 and 5.13 is written once for a min heap, and a max heap just swaps "smallest child" for "largest child".

Two consequences follow immediately, and both matter. First, in a min heap the minimum key sits at the root — the smallest value is one step away. Second, the property is local: it only compares a node with its parent, so a violation can be repaired by local swaps (the upheap and downheap of the next two sections).

5.11.4 The Structural Property

The structural property says: a heap must always be a complete binary tree. From Section 5.4.3, that means all the levels except the last are completely filled, and all the nodes at the last level are as left as possible — the tree packs its nodes without gaps. No node can have children while the nodes to its left, one level up, still lack theirs.

Why force the shape? Two payoffs. First, a complete tree of n keys has height about ${\log }_{2}n$ — the shortest height a binary tree can have for its size — so any walk from the root to a leaf is short, and the heap's operations (Sections 5.12 and 5.13) run in O(log n). Second, completeness is exactly what the vector representation of Section 5.10.3 needs to be efficient: a complete tree has no gaps, so the array has no wasted middle slots, and the parent/child arithmetic is exact.

5.11.5 A Worked Heap Check

Determine what kind of heap this is:

            25
          /    \
        22      17
       /  \    /  \
     19   22  14   15
    / \  / \ / \  / \
   18 14 21 3 9 11

Sense-check: the largest key, 25, is at the root — in a max heap the biggest value must sit on top, and it does. The check "every parent ≥ its children" passed at all six internal nodes, and the shape fills left-to-right without holes.

The picture uses the same filler rectangles under the leaves that you saw in Section 5.9 — they are not nodes; they just make the diagram look uniform. The rectangle representation appears in the Goodrich textbook; treat the rectangles as placeholders.

Stored with level numbering, the same heap fills an array starting at position 1: 25 at 1, children 22 and 17 at 2 and 3, and so on. Because the tree is complete, the array has no gaps: the children of the node at position 3 are at positions 6 and 7 — 14 and 15. That is the level numbering of this heap.

5.12 Heap Insertion and Upheap

5.12.1 The Insertion Procedure

We insert an element into an already existing heap — a heap that currently satisfies both the relational and the structural property. (Building a heap from scratch is a separate topic, studied later.)

Insertion has two steps:

1. Insert the new key K at the insertion node z — the next available location: the position where the next element will be added to the heap. Under completeness, that is the leftmost free slot of the last level (in the vector, the slot after the last occupied one).
2. Restore the heap-order property if it was broken. Inserting at the next available location preserves completeness automatically, but the relational property may now be violated — the new key may be smaller than its parent in a min heap. The restoration step is called upheap.

The second step is not optional. "Insert at the next available location and we are done" is wrong — the heap-order property may be lost the moment the new element lands.

Why must the new key land at the next available location and nowhere else? Because completeness is a shape contract: the last level fills from the left without gaps. Dropping the key anywhere else would create a hole, and a heap with a hole is not complete — the vector storage (Section 5.10.3) would no longer describe the tree.

5.12.2 Upheap: A Worked Insertion

Consider a min heap, where the parent must be small and children large. Suppose we insert the key 1, and it lands as the child of 6. Check the heap-order property: the parent 6 is supposed to be small, but the child 1 is smaller than 6 — violation. Upheap fixes it by swapping K along an upward path from the insertion node:

• Exchange 6 and 1. Now 1 is where 6 was, and 6 is down at the insertion node.
• Check again. The new parent of 1 is 2 — and 1 < 2, still a violation in a min heap. Exchange again: 1 comes up, 2 goes down.
• Check again. Now 1's parent satisfies the order, and the heap-order property is restored.

Each check-and-swap moves the new key one level up, until its parent is no larger than it (min heap) — or until it reaches the root. The restoration is complete when the path from the root to the insertion node is back in non-decreasing order.

       1
      / \
     2   5
    / \
   6   7
  /
 1        ← new key, left child of 6

       1
      / \
     2   5
    / \
   1   7
  /
 6

       1
      / \
     1   5
    / \
   2   7
  /
 6

The key insight of upheap: the new key only ever travels upward, one level per swap, and it stops the moment its parent is no larger than it. Everything below the insertion node was a valid heap before, and swapping keys does not change which values sit where — only who holds them — so no other part of the tree can be disturbed.

5.12.3 Upheap Complexity

What is the time complexity of upheap? It is $O(\log n)$ — the height of the tree. The traversal goes from the new node to the root along a single upward path; each level contributes one comparison and one possible swap. The number of steps is the number of levels, which is the height of the tree.

Why is the height of a complete tree $O(\log n)$? Each level holds about twice as many nodes as the one above: level 0 has 1 node, level 1 at most 2, level 2 at most 4, and so on. A complete tree of height $h$ holds $1+2+4+\cdots +2^h$ nodes in the first $h$ levels, which sums to $2^{h+1}-1$ — so $n\approx 2^{h+1}$ and $h\approx {\log }_{2}n$. How the height of a complete tree comes out to $\log n$ was derived earlier when recursion trees were studied — it is the same result, and you should be able to reproduce it. Upheap never visits the whole tree.

5.12.4 Student Questions and Answers

This question exposes the common mistake of "fixing" a whole heap after every change. The fix is local because the damage is local: a fresh key can only disagree with the nodes it climbed through, so a single path — not the whole tree — is all that needs repair.

5.13 Heap Removal and Downheap

5.13.1 The Removal Procedure

Removal from a heap means removing the root — in a min heap that is the minimum element, in a max heap the maximum, because the extreme value always sits at the root. If your application needs to remove some other, intermediate element, the heap is not the right structure (Section 5.13.4).

The removal procedure:

1. Exchange the root key with the key of the last node W. The last node is the rightmost node of the last level — in the vector representation, the last occupied slot.
2. Remove the last node. After the exchange, the value we wanted to delete is at the last position, and deleting the tail of the vector is a cheap operation.
3. Restore the heap-order property with downheap — swap the displaced key downward along a path from the root, at each step exchanging with the smallest child (min heap) or the largest child (max heap), until the order holds.

Notice the mirror of insertion (Section 5.12): insertion trades away completeness and restores order with an upward climb; removal trades away order and restores it with a downward climb. Both procedures only ever walk one path.

5.13.2 A Worked Removal (Min Heap)

Start with a min heap whose root is 2 and whose last node holds 7.

• Exchange root and last: 2 and 7 swap. The value 2 — the minimum — is now at the last position. Delete the last node. That is a single O(1) operation: in the vector representation, the index of the last node always equals the size of the vector (remember, slot 0 is unused), so we know exactly where the tail is and removing it is constant time. That is precisely why we exchange first.
• Restore. The heap-order property is now violated: 7 sits at the root. Its children are 5 and 6. In a min heap, downheap exchanges the displaced key with the smaller child — out of 5 and 6, that is 5. Exchange 7 and 5: 5 comes to the root, 7 moves down. Now check 7's children at its new position — the order holds, so downheap stops.

The heap is restored: root 5, and the subtree order valid again.

       2
      / \
     5   6

       7
      / \
     5   6

       7
      / \
     5   6

       5
      / \
     7   6

Which child — 5 or 6? We exchange with 5 because the heap-order property for a min heap only demands that each parent be no larger than its children. Swapping 7 with the smaller of its two children (5) keeps the root as small as possible and preserves the min-heap property; some implementations swap with 6 instead, and there is no logical or technical error in that — the property still holds. The convention is to pick the minimum child in a min heap (maximum child in a max heap), and that is what we do.

One edge case is worth noting. If the heap has a single node, the root and the last node are the same node: the "exchange" is a no-op, the tail deletion removes the only node, and no downheap is needed. And if the root's children are both leaves, downheap does at most one comparison-and-swap and then stops — the displaced key cannot sink further. The procedure handles both cases without any special rules, which is the mark of a clean algorithm.

5.13.3 Downheap Complexity

The time complexity of downheap is $O(\log n)$, for the same reason as upheap: the displaced key travels down a single path — one subtree, not the whole tree — and the path length is bounded by the height of the tree, which is $\log n$ for a complete tree. Every individual operation in upheap and downheap — swapping the elements at two positions — is $O(1)$; only the whole restore procedure is $O(\log n)$. If you can write a restore that runs in $O(1)$, you are the master; the best known general algorithm is the $O(\log n)$ one, and if your code is taking O(n), you should recognize that a better algorithm exists.

5.13.4 Student Questions and Answers

5.14 Heap Problem Solving: Last-Inserted Key and Delete-Max

5.14.1 The Problem Setup

The most reliable way to test whether the heap concepts above are actually understood is to work through a complete exam-style problem on a real heap. Consider the following max heap (the maximum key is at the root, parents larger than children):

             48
           /    \
         47      45
        /  \    /  \
      44   46  42   36
      / \  / \
    25 32 24 27
   (last level: 20, 29)

Read the picture level by level. Level 0: 48. Level 1: 47 and 45. Level 2: 44, 46, 42, 36 — 44 under 47, 46 under 47, 42 under 45, 36 under 45. Level 3 (last): 25 and 32 under 44, 24 and 27 under 46, 20 and 29 under 42, with 29 the rightmost node of the whole tree. Every parent is at least as large as its children — check a few: 47 ≥ 44 and 47 ≥ 46; 42 ≥ 20 and 42 ≥ 29 — so the heap order holds, and the shape is complete with the last level packed to the left.

Two questions are asked about this heap:

1. The last operation performed on the heap was inserting a key X, but we are not told which position it went into. Find all possible values of X.
2. Delete the maximum key from the heap. Find all the keys involved in one or more comparisons, and show the comparisons.

5.14.2 Which Keys Could Have Been Inserted Last

Answer: X could be 29, 36, 42, or 45 — nothing else.

The method: for each candidate key, imagine the heap before the insertion — with that key absent — and check that inserting it at the next available location, followed by upheap, produces exactly the picture above.

• X = 29. Take the picture above, remove 29: the heap order still holds everywhere, and 29's parent (42 in the layout shown) is larger than 29, so inserting 29 at the last available location needs no upheap at all. 29 is a valid last-inserted key.
• X = 36. Without 36, the heap's last available location sat next to 29 (with 29 the parent of 20 in the account given). Inserting 36 there violates the max-heap property, so upheap runs: 36 swaps with 29, 29 drops down, and the upheap stops because 42 is larger than 36 — the parent of 36's new position satisfies the order. The result matches the picture, so 36 is a valid last-inserted key. The general principle: every node on a valid upheap path is a candidate answer — the inserted key can end up anywhere along the path it climbed.
• X = 42. Same argument: insert 42 at the last available location, upheap climbs to 42's pictured position under 45, and stops because 45 > 42. Valid.
• X = 45. Insert 45 at the last available location, upheap climbs the right side to become the right child of the root, and stops because 48 > 45. Valid.

The rejected candidates are just as instructive:

• X = 48 — impossible. If 48 had been inserted last, the upheap would have run from the right-hand side, and 45 would have moved to the root. But before the insertion, the root would then have been 45 — impossible, because this is a max heap and the left child of the root is 47, which is larger than 45. A root of 45 with a left child of 47 violates the heap-order property. So 48 was already present in the heap before the last insertion; it cannot be X.
• X = 25, X = 32, X = 20 — impossible. Consider the vector implementation and the structural property. The tree is complete: the last level fills from the left. Nodes sitting in the interior of the last level — 25 and 32 on the left side, 20 left of 29 — were necessarily filled before the rightmost slot, and before the level could have any gaps. If one of them had been the last key inserted, the last level would have had empty slots to its left, breaking completeness. Only the rightmost last-level node (29) can be the final insertion without violating the structural property — which is why 29 is possible and 25, 32, 20 are not.

The complete answer: X ∈ {29, 36, 42, 45}. Two tests did the filtering: the relational test (the path the key climbed must satisfy heap order) and the structural test (the key must land at the next available location).

5.14.3 The Delete-Max Comparison Sequence

_  48  47  45  44  46  42  36  25  32  24  27  20  29

_  29  47  45  44  46  42  36  25  32  24  27  20

_  47  46  45  44  29  42  36  25  32  24  27  20

Answering a question like this correctly means you understand all the properties of the heap at once — insertion position, exchange-with-last, the child choice in downheap, and where the comparisons actually happen.

5.14.4 Student Questions and Answers

5.14.5 Exam Notes

The marking scheme that goes with those marks is strict about how you write the answer.

One more recognition tip, because the exam may not label the structure for you.

5.15 The Master Method Question: T(n) = T(n/2) + 2^n

5.15.1 The Quiz Question

A quiz question asked whether the master method applies to the recurrence

$$T(n)=T(n/2)+2^n$$

This is a subtle question, and the discussion that followed is worth keeping. In this recurrence, $a=1$, $b=2$, so $n^{{\log }_{b}a}=n^{{\log }_{2}1}=n^0=1$, and $f(n)=2^n$ — an exponential function. The structure matches the master method's input form $T(n)=aT(n/b)+f(n)$ with one recursive call of half size, but the extra term is the wild card.

5.15.2 The Intuition

Start with intuition, because the intuition is correct even where the formal rule is stricter. Where did the master method come from? From the recursion tree. In the recursion tree, $f(n)$ is the cost of the first invocation of the recursion — the work done at the root, other than the recursive part. Here $f(n)=2^n$, and the root's cost is exponential. Keep expanding the recursion tree and the picture stays the same: the exponential cost at the root dominates every other cost in the tree, because for any value of n, $2^n$ is greater than $n^{{\log }_{b}a}$ — which here is just 1. By intuition alone, then, this looks like case 3 of the master method: the root cost dominates.

The recursion-tree view explains the whole method in one sentence: the total cost is the sum over all nodes, and whichever term — the leaves' cost or the root's cost — grows fastest decides the answer. With $2^n$ at the root, every level below the root adds costs that are dwarfed by the first one.

5.15.3 The Technical Rule

The technical rule is stricter. The master method (as stated in Cormen) does not actually require $f(n)$ itself to be a polynomial — it requires the ratio to be polynomially larger. The precise condition:

$$\frac{f(n)}{n^{{\log }_{b}a}}\text{must be a polynomial}$$

That is the meaning of "polynomially larger": f(n) divided by $n^{{\log }_{b}a}$ should be a polynomial. Apply it here:

$$\frac{2^n}{n^{{\log }_{2}1}}=\frac{2^n}{1}=2^n$$

which is not a polynomial. So by the letter of the rule, the master method does not apply to this recurrence — the time complexity cannot be determined using the master method. That is the conclusion we go with: Cormen's position.

Why the ratio test and not the raw comparison? Because "bigger" is not enough for case 3 — the gap between $f(n)$ and $n^{{\log }_{b}a}$ must be polynomial. The ratio $2^n/1=2^n$ does not settle down into any $n^k$ shape; it grows faster than every polynomial, which is precisely the situation the master theorem does not cover. (Compare the classic near-miss $T(n)=2T(n/2)+n\log n$: the ratio is $\log n$, not polynomial, so that recurrence falls into the gap between cases 2 and 3 — same family of traps.)

There is a wrinkle worth knowing: some references — in particular, MIT's algorithms lectures, where Erik Demaine teaches — reach a different conclusion and place this recurrence in case 3. The divergence exists because the textbook's statement of the condition is easy to misread. Cormen does not say "f(n) should be polynomial"; it says f(n) should be polynomially larger, and that ratio test is exactly where the exponential fails. The two readings differ, and for this quiz both answers were credited — "master method not applicable" was accepted, and so was the case-3 reasoning. If you want to know which reading a course follows, check the exact wording of the master method statement in the textbook it uses.

5.15.4 Student Questions and Answers

5.15.5 A Closing Question and Answer

Exam Guidance Summary

The exam-relevant material of this lecture, collected in one place for revision:

• Depth versus height. Depth is for a node — the number of its ancestors. Height is for a tree — the maximum depth of any node, equivalently the maximum depth of an external node. These definitions may differ slightly from other books; follow these, and there will be no confusion.
• Terminology definitions. Root (no parent), internal node (at least one child — and the root is an internal node), external or leaf node (no children). Be clear about these; the terms are used from now on without re-explanation.
• Binary tree means "at most" two children. A node with a single child is still a binary tree. Many students get this wrong in exams and quizzes.
• Full versus complete. Full: every node other than the leaves has 2 children. Complete: full, plus all levels except the last completely filled, plus the last level as left as possible. Every complete tree is full; not every full tree is complete.
• Traversals. All traversals are O(n) — visiting all the nodes. In, pre, post are with respect to the root: in-order = left, root, right; pre-order = root, left, right; post-order = left, right, root. Deleting a tree uses post-order. Try the traversal exercises as homework.
• Reconstructing a tree from traversals. You need in-order plus one other traversal (pre-order or post-order) — in-order is compulsory, unless the tree is known to be full, in which case pre-order plus post-order suffice. Work the fixed steps on paper, never by intuition.
• No partial marking on tree construction. One wrong node cuts the whole tree; there is no partial credit. Show every step with reasons — bare numbers without explanation get cut in evaluation. Answers without explanation get no marks.
• Time complexities of tree methods. root, parent, swap, replace, is-internal, is-external, is-root are O(1) under level numbering; elements and positions are O(n); children(p) is O(children of p) — not O(n). Expect time complexity questions on the tree ADT methods.
• Read definitions, not just function names. In past questions (for example, on doubly linked lists), the definition of an operation differed from what the function name suggested. Find the running time from the definition given, not from the name. Pen and paper deduction — no programming.
• Heap. A heap is a binary tree plus a relational property (heap order) and a structural property (completeness). Min heap: keys non-decreasing from root to external nodes; max heap: non-increasing. Insertion at the next available location, then upheap, O(log n). Removal of the root, exchange with the last node, then downheap, O(log n). A 5-mark question on heap insertion/removal appeared in a previous exam; expect similar.
• Heap exam problem. Be able to find all possible last-inserted keys (the answer is the nodes on a valid upheap path — here 29, 36, 42, 45) and to list the exact comparison sequence in delete-max, showing each comparison. No explanation means no marks.
• Master method. Understand the difference between the intuition (cost of the first invocation — the root of the recursion tree dominates) and the formal condition (f(n)/n^(log_b a) must be a polynomial). For T(n) = T(n/2) + 2^n, the master method does not apply by Cormen's rule.
• Coverage so far. The midsemester portion covers up to chapter six, including the dictionary (a hash table); that is about eleven sessions of material. Coming topics: priority queue, then the dictionary.

Key Industry Applications

• File systems and storage — the folder structure of an operating system is a tree; file storage and database tables use trees. Every path like C:\Users\Name\Documents\report.docx is a route through the file-system tree.
• Database indexing — indexes are kept in tree structures for fast lookups. Instead of scanning a table row by row, the database walks an index tree to reach the matching keys in O(log n).
• HTML DOM — the Document Object Model stores an HTML document as a tree. Browser scripting and web scrapers navigate and edit web pages by walking this tree.
• Compilers — syntax trees represent program structure. The parser builds the tree, and later compiler phases walk it to check types and generate code.
• Text tools — auto character and spell checkers use trees. Prefix (trie) trees let a spell checker reject a misspelled word as soon as a prefix stops matching.
• Data compression — Huffman coding builds a binary tree to assign short codes to frequent symbols, shrinking files by making common characters cheap to store.
• Programming languages — the C++ set and map containers are implemented with tree concepts, giving O(log n) lookups and insertions on sorted keys.
• Chess engines — build a huge tree of moves, pruned at runtime with heuristics to pick an optimal move. The game tree is the data structure at the heart of every search-based game player.
• Pathfinding (AI) — the A-star (A*) algorithm searches over a tree, expanding candidate routes in best-first order to find the shortest path.
• 3D games — binary space partitioning (BSP), used in almost all 3D games, orders objects from front to back relative to the viewer (first-person shooters such as Call of Duty and BGMI) and is implemented on top of a tree.