3.4.1 · D5Trees
Question bank — Tree terminology — root, leaf, height, depth, degree, subtree
Before we start, we lock down every word this page leans on so nothing is used unearned.
Recall The words we lean on (tap to refresh)
- Root ::: the single node with no parent.
- Leaf ::: a node with no children (nothing hangs below it).
- Depth of ::: number of edges going up from to the root; root has depth .
- Height of ::: number of edges on the longest downward path from to a leaf; a leaf has height .
- Degree of a node ::: how many children it has.
- Subtree ::: a chosen node together with all its descendants, viewed as a tree in its own right (the chosen node becomes that little tree's root).
- Cycle ::: a path of edges that starts and ends at the same node without repeating an edge — a "loop." Trees forbid cycles entirely.
We count edges, not nodes, throughout — that is the convention this whole vault uses.
True or false — justify
Each statement is either true or false. Say which, and why — the "why" is the whole point.
Every tree with at least one node has exactly one root.
True. The definition requires exactly one node with no parent; zero roots would mean everyone has a parent (impossible without a cycle), and two disconnected pieces would be a forest (several trees), not one tree.
A tree with nodes can have edges if it is drawn carefully.
False. A tree always has exactly edges: every node except the root contributes one edge to its parent. An -th edge would create a cycle (a loop), and a tree has no cycles by definition.
The height of a tree equals the largest depth found among its nodes.
True. The deepest node sits at the far end of the longest root-to-leaf path, and that path length is the height of the root, which is the height of the tree.
If a node has depth , its height must be less than .
False. There is no forced relationship. A node at depth could have a very tall subtree below it (height ) or be a leaf (height ). Depth looks up; height looks down — they are independent measurements.
Every leaf in a tree sits at the same depth.
False. Leaves are defined only by having no children, so a leaf can appear at any depth. A node at depth with no children is a leaf, sitting far above deeper leaves.
Swapping the words "depth" and "height" in the recursive height formula still gives correct results.
False. The recursion builds upward from leaves. Depth builds downward from the root (). They flow in opposite directions and are not interchangeable.
A tree with exactly one node has height .
True. The single node is both root and leaf; it has no children, so the longest downward path has edges, giving height .
The degree of a tree can be larger than the degree of every individual node.
False. Tree degree is defined as the maximum node degree, so it always equals some node's degree — never exceeds all of them.
Removing the root of a tree always leaves you with exactly one smaller tree.
False. It leaves a forest — one tree per child of the old root. If the root had children, you get separate trees.
Any subtree is itself a valid tree.
True. A subtree (a node plus all its descendants) has the chosen node acting as root, since that node has no parent inside the subtree, and no new cycles appear — it satisfies every tree rule.
Spot the error
Each line contains a plausible but wrong claim. Find the flaw.
"The root has depth because it is the first level."
The error is counting nodes instead of edges. Depth = edges from root to the node; the root reaches itself in edges, so its depth is . (The root's level is level , not level .)
"This node has edges touching it, so its degree is ."
In graphs that would be right, but in trees degree = number of children only. One of those edges goes up to the parent and must not be counted — the true degree here is .
"Node is at depth , so it can't be a leaf."
Depth has nothing to do with leaf-ness. is a leaf if and only if it has no children; a childless node at depth is a perfectly valid leaf.
"Height of this leaf is because it is one node."
We measure edges below the node, not the node itself. A leaf has no children, so edges hang below it — its height is .
"A tree of height with degree can hold up to nodes, so any -node tree has height ... therefore height ."
The bound is only an upper limit. An -node degree- tree needs height at least , not , because nodes is the maximum height- can hold — the th node forces a new deeper level.
"To find the tree's height I just count how many leaves it has."
Leaf count measures width/branching, not depth. Height is the number of edges on the longest root-to-leaf path; a tree can have many leaves yet be short, or few leaves yet tall.
"Siblings are any two nodes at the same depth."
Same depth (same level) is necessary but not sufficient. Siblings must share the same parent. Two nodes on level under different parents are cousins, not siblings.
Why questions
These ask you to reconstruct the reason behind a definition, not just recite it.
Why does the "root has depth , leaf has height " convention make the recursion cleaner?
Because starting the base case at makes each edge you traverse add exactly . Then and both fall out with a clean "+1 per edge" — no correction terms.
Why can a tree never contain a cycle, given each non-root node has exactly one parent?
Following parent pointers upward from any node gives a unique, ever-rising path that must end at the root (the only parentless node). A cycle (a loop back to a node already visited) would require some node to eventually be its own ancestor, i.e. have two ways up — contradicting "exactly one parent."
Why do we measure height down and depth up rather than both the same way?
They answer different real questions. Depth = "how far am I from the boss (root)?" — a property fixed by position from the top. Height = "how deep does my branch go below me?" — a property of what hangs underneath. Opposite questions need opposite directions.
Why does level hold at most nodes when the tree degree is ?
Each node produces at most children, so each step down one level multiplies the possible count by . Starting from node at level , level has at most nodes.
Why is the empty forest given height rather than ?
We want the rule "adding one level adds one to the height" to hold everywhere. A one-node tree has height ; that one node is exactly one level above nothing, so "nothing" (the empty forest) must sit one step below , i.e. at . Choosing keeps the "+1 per level" pattern unbroken, so recursive code like still gives the right answer when a missing child contributes the empty-forest value (a leaf then computes ). ✅
Why is the maximum node count and not just ?
counts only the bottom level. The full tree stacks all levels through , so we must sum , which collapses to (derived stepwise below).
Why is "height of the tree = height of the root" the same as "max depth of any node"?
The root's tallest downward path ends at the deepest leaf. That path's edge-count is simultaneously the root's height and that leaf's depth — the same edges counted from both ends.
The geometric-series bound, derived step by step
Edge cases
The scenarios people forget to test. Handle each explicitly.
Single-node tree: what are its root, leaves, height, depth, and degree?
The lone node is the root (no parent) and a leaf (no children). Its depth is , its height is , and its degree is . Everything degenerate collapses onto one node.
"Nothing at all" (zero nodes): is that an empty tree or an empty forest, and what height?
It is an empty forest, not a tree — a tree must have exactly one root, so it can never have zero nodes. We give this empty forest height by convention, chosen so that a one-node tree (height ) is consistently one level taller than nothing. Always state this convention.
A "path" tree — every node has exactly one child except the last: what is its height and degree?
It is a straight chain of nodes, so its height is (one edge per link) and its tree degree is (each node has at most one child). It is the tallest, thinnest tree possible for its node count.
A "star" tree — one root with children and nothing deeper: height and degree?
Its height is (root to any child is one edge) and its tree degree is (the root is the bossiest node). It is the shortest, widest extreme — the opposite of a path.
Is the root ever also a leaf?
Yes — in the single-node tree. With no children it satisfies "leaf," and with no parent it satisfies "root." In any tree of or more nodes the root has at least one child, so it can no longer be a leaf.
Can a node be its own ancestor or descendant?
No. Ancestors lie strictly on the path up to the root; descendants lie strictly below. A node lies on neither side of itself, and allowing it would require a cycle, which trees forbid.
What is the depth of a leaf that also happens to be the deepest node?
Its depth equals the tree's height, since it sits at the end of the longest root-to-leaf path. This is the only case where a leaf's depth matches the tree height — a common source of the "depth = height" confusion.
If every node in a tree has degree , how many nodes are there?
Exactly one. Degree means no node has children, so no node can have a parent either — only the lone root can exist. Two nodes would force one to be the other's child, giving that parent degree .
Connections
- Binary Trees — the degree special case where these traps recur constantly.
- Balanced Trees (AVL, Red-Black) — the whole point is controlling height; get height right first.
- Tree Traversals — depth/level confusion resurfaces in BFS vs DFS.
- Recursion — the height recursion here is the model for every tree algorithm.
- Graphs — the degree definition genuinely differs; this page's degree trap comes from there.