213: Trees, Terminology, Traversals, Height, Depth, and Recursive/Iterative DFS

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply tree terminology in a realistic implementation;
explain and apply preorder, inorder, and postorder traversal in a realistic implementation;
explain and apply level-order traversal in a realistic implementation;
explain and apply recursive DFS in a realistic implementation;
explain and apply iterative DFS in a realistic implementation.

The goal is not just to recite traversal names. You should be able to choose an order from the dependency in the problem, state the invariant that makes the implementation correct, and recognize when recursion or an explicit stack is the safer engineering choice.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same concern appeared. Perhaps you processed nested configuration, rendered a component hierarchy, walked a file tree, or represented organizational relationships. The example does not need to have been called a “tree”; the point is to connect the vocabulary to a structure you have already handled.

Do not try to memorize a template in isolation. The useful skill is making a defensible decision in both an interview-sized problem and a production data-processing problem. That means reasoning from constraints such as ordering, memory, maximum height, malformed input, and the required output.

Terminology

Tree terminology: The root is the entry point. A parent owns the relationship to its child, siblings share a parent, and a leaf has no children. Depth, height, subtree, and degree describe different properties and should be used precisely.
Preorder inorder postorder: Preorder processes a node before its children, inorder places a binary-tree root between its left and right subtrees, and postorder processes the children before the root.
Level-order traversal: BFS processes nodes by depth using a queue. It is a natural choice for shortest unweighted depth, level summaries, and nearest-node questions.
Recursive DFS: Recursion mirrors the tree structure and is concise, but the call-stack depth is tied to the tree height.
Iterative DFS: An explicit stack gives direct control over traversal state and avoids depending on the language's recursion limit.
Bottom-up versus top-down state: Height and diameter often combine results returned from children, which is bottom-up. Path constraints and accumulated values are often carried from a parent into a child, which is top-down.

The distinctions around depth and height are especially important. The depth of a node is measured from the root downward. The height of a node is measured from that node downward to its deepest descendant. A convention must be chosen: with edges as the unit, a leaf has height 0 and an empty tree has height -1; with nodes as the unit, a leaf has height 1 and an empty tree has height 0. Either convention can work, but mixing them produces off-by-one errors in balancedness, diameter, and level calculations.

Mental model

Treat Trees, Terminology, Traversals, Height, Depth, and Recursive/Iterative DFS as a design problem with observable inputs, outputs, invariants, and failure modes. Trees model hierarchical relationships and recursive structure. You should become fluent in traversal orders and in deciding which properties need information returned bottom-up versus state carried top-down. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe.

For now, keep the model simple: a tree is a set of nodes with one entry point and no cycles. Each node may have zero or more children. A binary tree limits that child count to two; it does not, by itself, promise ordering, uniqueness, or balance. If the input can contain cycles or shared nodes, it is graph-like and may require a visited set rather than a plain tree traversal.

The traversal names describe when the current node is processed relative to its children:

             A
           /   \
          B     C
         / \
        D   E

preorder:   A B D E C   (node, left, right)
inorder:    D B E A C   (left, node, right)
postorder:  D E B C A   (left, right, node)
level-order: A B C D E  (by depth)

This diagram is a conceptual model, not a claim that every tree has left and right children. Inorder has a standard meaning only when the tree has an ordered binary-tree shape. For a general n-ary tree, preorder and postorder still make sense, while “inorder” needs a separately defined child-position rule.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a traversal snippet. First state what must remain true. Then choose the mechanism that enforces it. For example, if the requirement is “return the first node at minimum depth,” the queue's invariant should be that nodes are removed in nondecreasing depth order. If the requirement is “evaluate a directory after its children,” postorder is the direct expression of that dependency.

Deep dive

1. Tree terminology

When a bug report says “the child is missing,” ask which relationship is actually missing. The root has no parent in the represented tree. A parent has one or more outgoing child relationships; a child is one step below that parent. Siblings have the same parent. A leaf has no children. A node and all of its descendants form a subtree. The degree of a node is its number of children, while the degree of the tree is often defined as its maximum node degree.

Depth and height use opposite directions. Starting at the root and counting edges gives a node's depth. Starting at a node and following the longest downward path gives that node's height. A tree with one root has root depth 0; under the edge-based convention, its root height is also 0. That numerical coincidence does not make the concepts interchangeable.

Root, parent, child, sibling, leaf, depth, height, subtree, and degree should be used precisely. A binary tree allows at most two children but is not automatically ordered or balanced. A binary search tree adds an ordering rule; a balanced tree adds a height constraint. Those are additional properties, not consequences of the word “binary.”

Decision rule: Use tree terminology deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. For instance, document whether null means an empty tree, whether duplicate values are allowed, and whether child order is meaningful.

2. Preorder inorder postorder

Preorder, inorder, and postorder are depth-first traversal timings. For a binary node, the three placements are:

preorder:   visit(node), traverse(left), traverse(right)
inorder:    traverse(left), visit(node), traverse(right)
postorder:  traverse(left), traverse(right), visit(node)

The needed order follows the dependency of the computation. Preorder is useful when the parent must be emitted before descendants, such as serializing a hierarchy or copying it. Inorder is useful for an ordered binary search tree because it visits values in sorted order, but that sorted result depends on the search-tree invariant. Postorder is useful when a parent depends on completed child work, such as freeing a hierarchy or calculating a directory aggregate.

For the sample tree, preorder is A B D E C, inorder is D B E A C, and postorder is D E B C A. A common mistake is to use inorder because the name is familiar and then assume it sorts arbitrary binary-tree values. Traversal order cannot create an ordering invariant that the input does not have.

Decision rule: Use preorder, inorder, and postorder deliberately when they make the contract or invariant easier to prove. If a short recursive function hides whether children are visited in a meaningful order, make that order explicit in the node type or implementation.

3. Level-order traversal

Breadth-first search processes nodes by depth. A queue holds the frontier: remove the next node, inspect it, and append its children to the back. Because children are appended after all nodes already in the current frontier, nodes at a smaller depth are processed first.

queue: [A]
visit A, enqueue B C  -> [B, C]
visit B, enqueue D E  -> [C, D, E]
visit C               -> [D, E]
visit D, then E       -> []

BFS processes nodes by depth using a queue and is natural for shortest unweighted depth, level summaries, and nearest-node questions. It can use more memory than DFS on a wide tree because the queue may contain an entire level. With n nodes, a complete traversal is O(n) time; auxiliary space is O(w), where w is the maximum width, and can be O(n) in the worst case.

Decision rule: Use level-order traversal deliberately when it makes the contract or invariant easier to prove. If the requirement only asks for a postorder aggregate and the tree may be very wide, a DFS may use less peak memory.

4. Recursive DFS

Recursion mirrors tree structure and is concise, but stack depth equals tree height. A skewed tree can therefore overflow even when node count is moderate. The recursive base case must handle the empty child before the function reads its value or children.

For a recursive traversal, each call owns one node and returns only after its required child calls finish. That makes the placement of visit(node) the essential difference between preorder, inorder, and postorder. For a tree with n nodes, the traversal takes O(n) time and O(h) auxiliary space, where h is the tree height, including the call stack.

type TreeNode = {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

function preorder(node: TreeNode | null, output: number[] = []): number[] {
  if (node === null) return output;
  output.push(node.value);
  preorder(node.left, output);
  preorder(node.right, output);
  return output;
}

The implementation is short because the call stack stores the return point and the current subtree. That convenience is a real resource cost. A balanced tree has height O(log n), while a chain-shaped tree has height O(n). If input height is attacker-controlled or simply large, iterative DFS is often a safer boundary choice.

Decision rule: Use recursive DFS deliberately when it makes the contract or invariant easier to prove. If the credible height can exceed the runtime's safe call-stack depth, use an explicit stack or validate the height before recursing.

5. Iterative DFS

An explicit stack gives control over traversal order and avoids recursion limits. Push children in the reverse order of the order you want to visit, because a stack is last-in, first-out. To reproduce recursive preorder (node, left, right), push the right child first and the left child second.

function iterativePreorder(root: TreeNode | null): number[] {
  if (root === null) return [];

  const output: number[] = [];
  const stack: TreeNode[] = [root];

  while (stack.length > 0) {
    const node = stack.pop()!;
    output.push(node.value);
    if (node.right !== null) stack.push(node.right);
    if (node.left !== null) stack.push(node.left);
  }

  return output;
}

The non-null assertion is safe here because the loop condition establishes that pop() is called only while the stack contains an item. In production TypeScript, the assertion does not validate external data at runtime; the tree still needs boundary validation if it comes from an untrusted source.

Inorder and postorder can also be implemented with an explicit stack, but they need more state than preorder. One common approach stores a node plus a phase, or pushes a node back after scheduling its children. The invariant is that the stack represents unfinished work, not merely values that happen to be nearby. With n nodes, iterative DFS is O(n) time and O(h) auxiliary space in the usual one-stack formulation, with O(n) worst-case space for a skewed tree.

Decision rule: Use iterative DFS deliberately when it makes the contract or invariant easier to prove. If the stack state becomes harder to review than the recursive version and the maximum height is demonstrably safe, recursion may be the clearer implementation.

6. Bottom-up versus top-down state

Height and diameter often combine child results bottom-up; path constraints and accumulated values are often carried top-down. Many bugs come from mixing local and global state.

For height, a node asks each child for its height and returns one plus the larger result. Under the edge-based convention, an empty child returns -1, so a leaf returns 0:

function height(node: TreeNode | null): number {
  if (node === null) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

For a diameter measured in edges, the best path through a node is leftHeight + rightHeight + 2. The global answer must be updated at every node while the function returns only the height needed by its parent. This is a useful example of local return state and global aggregate state being different responsibilities. A production implementation should state whether diameter is measured in edges or nodes.

By contrast, a root-to-node path sum carries an accumulated value downward. That is top-down state: the child receives the parent's value plus the current contribution. Do not return a value from a child and then treat it as though it described every path through that child; define whether the value is local to one subtree, attached to one path, or a global best.

Decision rule: Use bottom-up versus top-down state deliberately when it makes the contract or invariant easier to prove. If one function is simultaneously tracking several meanings of “depth,” split the state or name each quantity explicitly.

Worked example

Consider both an interview-sized problem and a production data-processing problem. In each case, reason from constraints rather than memorizing a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode.

For an interview problem, “return the preorder values of a binary tree” gives a concrete contract: the input is either a valid tree root or null, the output is an array in node-left-right order, and every reachable node is emitted once. The empty tree returns []. If the structure can contain cycles or shared nodes, it is not an ordinary tree and the contract must say whether repeated references are visited once or once per path.

For a production data-processing problem, “compute a directory's aggregate size” introduces more boundaries. Parsing or validation belongs at the boundary; tree/domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes malformed nodes, retries, partial reads, and stale data much harder to reason about.

The following small example is deliberately generic. Its point is to demonstrate stating an invariant before selecting the data structure, not to replace the tree examples above:

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is an assumption hidden in this example: 0 is the correct result for an empty input and for an input containing only negative values. If the requirement is instead “return the maximum supplied number,” that default is wrong and the contract needs either a non-empty input guarantee or an explicit empty-input result. This is the same kind of boundary assumption that causes tree algorithms to fail on null roots.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. In the tree version, include a single-node tree, a skewed tree, duplicate values, and a malformed or cyclic structure if external input can create one. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For tree processing, also ask whether the maximum node count and height are bounded, whether a traversal can hold an entire level in memory, and whether a malformed payload can cause nontermination or excessive recursion.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. A recursive traversal may be perfectly appropriate for a trusted, bounded AST and inappropriate for an unbounded user-supplied hierarchy. The algorithmic O(n) label does not answer peak memory, stack safety, validation cost, or operational observability.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Do not deserialize an arbitrary nested object and assume it is a valid acyclic tree merely because its TypeScript type says so.

Guided lab

Implement recursive and iterative preorder, inorder, and postorder, plus level order. Then compute tree height, balancedness, and diameter while distinguishing node depth from subtree height. State your height convention before writing tests, and state whether diameter is counted in edges or nodes.

For iterative inorder and postorder, do not copy a stack pattern without explaining its state. A useful invariant for inorder is that the stack contains the path to the next node whose left subtree has been exhausted. For postorder, the stack must preserve the fact that a node is not ready until both child subtrees have been processed.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

At minimum, test the empty tree, a single node, a balanced tree, a left-skewed tree, a right-skewed tree, and a tree with missing children in different positions. For a binary-search-tree-specific inorder claim, include values that demonstrate the ordering invariant; do not treat arbitrary node values as sorted just because the traversal is inorder.

Edge cases and failure modes

Tree terminology: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Preorder inorder postorder: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Level-order traversal: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Recursive DFS: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.
Iterative DFS: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes.

In addition, be explicit about the edge cases that are specific to tree algorithms. An empty tree can expose a height convention error. A one-node tree can expose an edge-versus-node diameter mismatch. A skewed tree can expose recursion overflow or unexpected O(n) auxiliary space. Duplicate values can show whether the algorithm relies on identity or value equality. Shared child references and cycles can invalidate the assumption that every recursive descent reaches a new node; if those structures are possible, track visited node identity and define the desired semantics.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. For a traversal, log or inspect the visit sequence and the stack or queue contents on a five-node tree. If the sequence is wrong, first check child-push order and the position of the visit operation. If height is wrong, check the empty-child base case and the chosen counting convention. If execution never finishes, inspect whether the input contains a cycle or shared reference that the algorithm was never designed to handle.

Interview questions

What problem does Tree terminology solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Preorder inorder postorder solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Level-order traversal solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Recursive DFS solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Iterative DFS solve, and what trade-off or failure mode would make you choose a different approach?

When answering, include the invariant and complexity, not just the definition. A strong answer distinguishes O(n) traversal time from O(h) DFS space and explains why BFS space is commonly described using maximum width. It also says what happens for an empty tree and what assumptions make a structure a tree rather than a general graph.

Checkpoint

Without notes, explain Trees, Terminology, Traversals, Height, Depth, and Recursive/Iterative DFS to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

If you need a prompt for self-checking, explain why preorder and postorder differ, why inorder is special to an ordered binary-tree arrangement, when a queue is preferable to a stack, and how a height convention affects the result for an empty tree. Finish by naming the resource that can become unsafe first for a very tall tree.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.