☕ DSA Java Articles

Topics › Binary Trees › Traversals

Preorder Traversal

Easy TUF ID 137 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return the values of its nodes in preorder: first the node itself, then its entire left subtree in preorder, then its entire right subtree in preorder. An empty tree (a null root) has an empty traversal.

Constraints: the number of nodes is between 0 and 10^5 here (LeetCode uses at most 100), and values are arbitrary 32-bit integers. Duplicate values are allowed; the traversal is about nodes, not values.

Trees in the examples are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

    1
     \
      2
     /
    3
root = [1, null, 2, 3]
answer = [1, 2, 3]        // 1 first; its left subtree is empty; then the subtree rooted at 2

Example 2

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
answer = [1, 2, 4, 5, 3, 6, 7]   // the whole left subtree (2, 4, 5) comes before anything on the right

The name tells you where the root goes: preorder puts the root before its subtrees, inorder puts it between them, postorder puts it after. Preorder is the natural order for copying a tree or writing it out, because every parent is produced before its children, so a reader can rebuild the tree top-down.

Approach 1: Recursion

Intuition. A binary tree is defined recursively: it is either empty, or a root with a left subtree and a right subtree, each of which is again a binary tree. Preorder follows the same shape: the preorder of a tree is the root, followed by the preorder of the left subtree, followed by the preorder of the right subtree. Code that mirrors this definition is three lines long.

One practical detail: instead of having each call return a new list and concatenating them (which copies elements again at every level, up to O(n^2) work on a skewed tree), we pass one shared output list down and let every call append to it.

Algorithm.

  1. If the current node is null, return; an empty subtree contributes nothing.
  2. Append the node’s value.
  3. Traverse the left subtree.
  4. Traverse the right subtree.
static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    preorder(root, out);
    return out;
}

private static void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;                 // empty subtree: nothing to visit
    out.add(node.val);                        // Root
    preorder(node.left, out);                 // Left
    preorder(node.right, out);                // Right
}

Why it works. By induction on the size of the subtree: a call on an empty subtree appends nothing, which is correct. For a larger subtree, the call appends the root, then (by the induction hypothesis) exactly the left subtree’s nodes in preorder, then exactly the right subtree’s nodes in preorder. That is the definition.

Complexity. Time O(n): every node is the argument of exactly one call that does constant work, plus n + 1 calls on null children that return at once. Space O(h) for the call stack, where h is the height: about log n for a balanced tree but n for a skewed one. Java’s default thread stack typically fits somewhere in the tens of thousands of frames like these, so a chain of 10^5 nodes can throw StackOverflowError. That is the main reason interviewers ask for the iterative versions below.

Approach 2: Iterative with a stack

Intuition. Recursion uses the call stack to remember work that is still pending. We can keep that memory ourselves in an explicit stack. In preorder the node is output the moment we take it; after that, the work left for this node is “the left subtree, then the right subtree”. A stack is last-in-first-out, so we push the right child first and the left child second. The left child is popped next, and everything it pushes lands on top of the waiting right child, so the whole left subtree is finished before the right child surfaces.

Algorithm.

  1. If the root is null, return an empty list.
  2. Push the root.
  3. While the stack is not empty: pop a node, append its value, push its right child if present, then its left child if present.
static List<Integer> iterative(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);
        if (node.right != null) stack.push(node.right);   // pushed first, popped last
        if (node.left != null) stack.push(node.left);     // pushed last, popped next
    }
    return out;
}

Dry run on Example 2. The stack is written bottom to top, so the right end is the top.

Step Popped Output so far Stack after the pushes
1 1 1 [3, 2]
2 2 1 2 [3, 5, 4]
3 4 1 2 4 [3, 5]
4 5 1 2 4 5 [3]
5 3 1 2 4 5 3 [7, 6]
6 6 1 2 4 5 3 6 [7]
7 7 1 2 4 5 3 6 7 []

Notice that node 3 waits at the bottom for the entire left subtree. That is exactly the “come back later for the right side” information that recursion keeps in its stack frames.

Complexity. Time O(n): each node is pushed once and popped once. Space O(h): at any moment the stack holds the current node’s left child plus at most one waiting right child for each ancestor on the current path.

Use ArrayDeque as the stack. The old java.util.Stack class extends Vector, synchronises every call and is kept only for backward compatibility.

Approach 3: Morris traversal

Intuition. Both previous approaches need O(h) memory to find the way back up from a left subtree to its parent. Morris traversal stores that “way back” inside the tree itself, using pointers that are null anyway. Before descending into the left subtree of cur, find the rightmost node of that left subtree (in inorder it is the node visited just before cur, called its predecessor). Its right pointer is null, so we temporarily point it at cur. This link is called a thread. When the walk later finishes the left subtree, it follows the thread back to cur, sees that the predecessor already points at cur, removes the thread, and moves to the right subtree.

Every node with a left child is therefore reached twice. For preorder we output it on the first arrival, before going left. Nodes without a left child are reached once and output immediately.

Algorithm.

  1. Set cur = root.
  2. While cur is not null:
    • If cur has no left child, output it and move to cur.right (which may be a thread back up).
    • Otherwise let pred be the rightmost node of cur.left, stopping early if pred.right == cur.
      • If pred.right is null (first arrival): output cur, set pred.right = cur, move to cur.left.
      • Otherwise (second arrival): set pred.right = null to restore the tree, move to cur.right.
static List<Integer> morris(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            out.add(cur.val);                             // no left subtree: visit and go right
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;                     // rightmost node of the left subtree
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {                     // first arrival: visit, leave a thread back, go left
                out.add(cur.val);
                pred.right = cur;
                cur = cur.left;
            } else {                                      // second arrival: left subtree done, remove the thread
                pred.right = null;
                cur = cur.right;
            }
        }
    }
    return out;
}

Complexity. Time O(n). The predecessor searches look expensive, but each one walks down the right edges of one left subtree, and every edge of the tree is walked by at most two such searches (once to create a thread, once to remove it). Space O(1) besides the output list.

The price is that the tree is temporarily modified. That is unsafe if another thread reads the tree at the same time, and if the loop were interrupted half-way the tree would be left with threads in it. The test in the Java file runs the recursive traversal again after Morris to confirm the tree was restored.

Edge cases and pitfalls