Iterator for Trees

Beginner Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

A tree iterator encapsulates the current position (often with an explicit stack for inorder). This keeps the internal representation hidden and algorithms work against hasNext/next.

Fail-fast behavior is analogous to lists: structural changes during iteration are risky.

Where used

Lazy traversal of large hierarchies, UI tree models, termination upon finding a match without needing to materialize the entire structure.

Depth

A tree iterator must store the unvisited control state between calls. For a sorted output of a search tree, it typically maintains a path of open nodes; after an output, the corresponding child subtree is revealed.

Each node is stored once and removed once. As a result, the total costs are linear, even though a single next call can add several path nodes. These peaks are distributed over the entire traversal.

Structural changes during iteration can invalidate paths. A fail-fast check detects many such changes but does not guarantee synchronization.

Difficulty levels

Specify the stored path after each next.
Justify the amortized costs of a complete traversal.
Specify the behavior of an iterator on changes.

Pitfalls

Simply storing the last output node is insufficient without parent references. hasNext should neither output nodes nor consume the traversal state.

University approvals: 0

Tasks

Question 1

Why does an inorder iterator often use a stack?

Because trees are arrays.

To keep the descent and return path without recursion.

Because hashing is necessary.

Because generics are missing

Question 2

Why can the total costs of all next calls remain linear?

Each node is stored only a limited number of times throughout the entire run.

Each call accesses directly via array index.

The iterator skips inner nodes.

The tree is copied into a list beforehand.

Question 3

Collect the tree values in preorder order.

Hint

An ArrayList<Integer> is created with new ArrayList<>(). A helper method can take the list and the current node as parameters.

import java.util.ArrayList;
import java.util.List;
public class TreePreorder {
  public static class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int value) { this.value = value; }
  }
  public static List<Integer> preorder(TreeNode node) {
    // TODO
    return null;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy