Recursive preorder traversal of a binary tree

You're in a technical interview and the interviewer draws a binary tree on the whiteboard. "Walk me through how you'd visit every node in this tree, starting from the root, always going left before right, and processing each node before its children." That's pre-order traversal in a nutshell, and it's one of the first tree problems you'll encounter in interview prep. This problem is also known as "Binary Tree Preorder Traversal" on other platforms like LeetCode and NeetCode.

TL;DR

Pre-order traversal visits each node in root-left-right order. Use a recursive helper that accepts the current node and a result list: if the node is not null, add its value to the list, then recurse on the left and right children. This runs in O(n) time and O(n) space. The recursive builder pattern keeps the public method clean by delegating the accumulation logic to a private helper.

Why This Problem Matters

Pre-order traversal is foundational. It's the building block for tree serialization, deep copying, and prefix expression evaluation. More importantly, solving it teaches the recursive builder pattern, a technique you'll reuse in dozens of tree and graph problems. Once you can write a clean recursive traversal, problems like path sums, tree serialization, and subtree matching become much more approachable.

Binary Trees and Traversal Orders

A binary tree is a hierarchical data structure where each node has at most two children. There are three classic depth-first traversal orders, and the difference comes down to when you process the current node relative to its children.

For this simple tree with root A, left child B, and right child C:

• Pre-order (root, left, right): A, B, C
• In-order (left, root, right): B, A, C
• Post-order (left, right, root): B, C, A

The prefix "pre" tells you the root is visited before its subtrees. That single difference drives the entire algorithm.

Understanding the Problem

Given: The root TreeNode of a binary tree Task: Return a list of node values visited in pre-order Constraint: Solve it recursively

Here's the example from the problem:

For this tree, pre-order traversal visits nodes in the order: [1, 2, 4, 5, 3, 6]. Starting at the root (1), we go left to 2, then left again to 4. Since 4 has no children, we backtrack and visit 5. Then we backtrack to the root and visit the right subtree: 3, then its right child 6.

The annotated diagram below shows the visit order at each node:

Edge Cases to Consider

1. Empty tree (null root): Return an empty list
2. Single node: Return a list with just that node's value
3. Left-skewed tree: All nodes chained to the left, no right children
4. Right-skewed tree: All nodes chained to the right, no left children

Solution Approach

The recursive structure of pre-order traversal maps directly to three steps:

1. Process the current node (add its value to the result)
2. Recurse on the left child
3. Recurse on the right child

The base case is a null node, where we simply do nothing.

The Recursive Builder Pattern

Rather than having the recursive function create and return new lists at each level (which wastes memory on list concatenation), we pass a single result list through all the recursive calls. The public method creates this list, hands it to a private helper, and returns it when traversal finishes.

This is sometimes called the "accumulator pattern" in functional programming. It keeps the public API simple while letting the recursion do the heavy lifting.

Prefer a different language? Jump to solutions in other languages.

Implementation

public class Solution {
  public List<Integer> preOrder(TreeNode root) {
    // Create the result list once and pass it through recursion
    return buildPreOrder(root, new ArrayList<>());
  }

  private List<Integer> buildPreOrder(TreeNode node, List<Integer> result) {
    if (node != null) {
      // Step 1: Process current node
      result.add(node.data);
      // Step 2: Recurse left
      buildPreOrder(node.left, result);
      // Step 3: Recurse right
      buildPreOrder(node.right, result);
    }
    return result;
  }
}

Let's trace through the execution with our example tree:

The recursion follows the tree structure naturally. Each call to buildPreOrder handles one node: add the value, go left, go right. When a null node is reached, the method returns immediately and the call stack unwinds back to the parent.

Why This Works

Think of the recursion as a depth-first exploration. At every node, you do your work first (add the value), then fully explore the left branch before touching the right branch. The call stack acts as an implicit "to-do list" that remembers where to continue after each left subtree is exhausted.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node, the work is O(1): one list append and two recursive calls. The total work across all nodes is O(n).

Space Complexity: O(n)

Two factors contribute:

• Result list: Stores all n node values, so O(n)
• Call stack: The maximum recursion depth equals the tree height h. For a balanced tree, h = O(log n). For a completely skewed tree (essentially a linked list), h = O(n).

The overall space is O(n) because the result list alone requires that much.

Common Pitfalls

1. Creating new lists in each recursive call: Some candidates write return [node.data] + preOrder(node.left) + preOrder(node.right). This works but creates O(n) intermediate lists and turns a linear algorithm into O(n^2) due to list concatenation costs. Use the builder pattern instead.

2. Forgetting the null check: Without the base case, the recursion will throw a null pointer exception on leaf nodes.

3. Confusing traversal orders: Pre-order puts the root first. If you accidentally process the root between the left and right recursive calls, you've written in-order traversal instead.

4. Returning void from the helper: The helper can either return void (modifying the list in place) or return the list for chaining. Both work, but returning the list makes the public method a clean one-liner.

Interview Tips

When solving this in an interview:

1. Clarify the definition: "Should I use recursion or is an iterative approach acceptable?" The problem asks for recursion, but mentioning the iterative stack-based alternative shows breadth.

2. Start with the base case: Articulate that a null node returns without doing anything. This shows you think about edge cases first.

3. Name the pattern: Calling it "the recursive builder pattern" or "accumulator pattern" signals experience with tree problems.

4. Mention the iterative alternative: After solving recursively, briefly describe the stack-based iterative approach. Push right child first, then left, so that left is popped and processed first.

5. Discuss space tradeoffs: The recursive approach uses O(h) stack space. For very deep trees, the iterative approach avoids stack overflow risk.

Comparing Traversal Orders

Understanding where pre-order fits among the tree traversal family helps in interviews when the follow-up question is "now do it in-order" or "now do post-order."

The recursive structure for all three DFS traversals is identical. The only difference is where you place the result.add(node.data) call relative to the recursive calls.

Key Takeaways

• Pre-order traversal follows root-left-right order, and the recursive implementation maps directly to this: process the node, recurse left, recurse right.
• The recursive builder pattern (passing an accumulator list through recursive calls) avoids the O(n^2) cost of creating and merging intermediate lists.
• Time complexity is O(n) since each node is visited once. Space is O(n) for the result list plus O(h) for the call stack.
• Switching between pre-order, in-order, and post-order is just a matter of moving the result.add() call. Master one and you've effectively mastered all three.
• The iterative alternative uses an explicit stack: push right before left so that left is processed first. Mention this to show depth of understanding.

Practice Makes Perfect

Once you're comfortable with pre-order traversal, try these related problems to solidify your understanding of tree traversals:

• Recursive in-order traversal (swap when you add the node value)
• Height of a binary tree (same recursive structure, different accumulation)
• Convert a binary tree to its mirror image (process children in reversed order)

This problem and many more are available on Firecode, where over 50,000 engineers have sharpened their skills for technical interviews. Whether you're just starting with trees or preparing for your next big interview, consistent practice on problems like this builds the muscle memory you need to perform under pressure.

Solutions in Other Languages

Python

class Solution:
    def pre_order(self, root):
        return self.build_pre_order(root, [])

    def build_pre_order(self, node, result):
        if node is not None:
            result.append(node.data)
            self.build_pre_order(node.left, result)
            self.build_pre_order(node.right, result)
        return result

JavaScript

class Solution {
  preOrder(root) {
    return this.buildPreOrder(root, []);
  }

  buildPreOrder(node, result) {
    if (node !== null) {
      result.push(node.data);
      this.buildPreOrder(node.left, result);
      this.buildPreOrder(node.right, result);
    }
    return result;
  }
}

TypeScript

class Solution {
  preOrder(root: TreeNode | null): number[] {
    return this.buildPreOrder(root, []);
  }

  buildPreOrder(node: TreeNode | null, result: number[]): number[] {
    if (node !== null) {
      result.push(node.data);
      this.buildPreOrder(node.left, result);
      this.buildPreOrder(node.right, result);
    }
    return result;
  }
}

C++

class Solution {
public:
  std::vector<int> preOrder(TreeNode *root) {
    std::vector<int> result;
    buildPreOrder(root, result);
    return result;
  }

private:
  void buildPreOrder(TreeNode *node, std::vector<int> &result) {
    if (node != nullptr) {
      result.push_back(node->data);
      buildPreOrder(node->left, result);
      buildPreOrder(node->right, result);
    }
  }
};

Go

func (s *Solution) PreOrder(root *TreeNode) []int {
    return s.buildPreOrder(root, []int{})
}

func (s *Solution) buildPreOrder(node *TreeNode, result []int) []int {
    if node != nil {
        result = append(result, node.Data)
        result = s.buildPreOrder(node.Left, result)
        result = s.buildPreOrder(node.Right, result)
    }
    return result
}

Scala

class Solution {
  def preOrder(root: TreeNode): List[Int] = {
    buildPreOrder(root, mutable.ArrayBuffer[Int]()).toList
  }

  private def buildPreOrder(node: TreeNode, result: mutable.ArrayBuffer[Int]): mutable.ArrayBuffer[Int] = {
    if (node != null) {
      result.append(node.data)
      buildPreOrder(node.left, result)
      buildPreOrder(node.right, result)
    }
    result
  }
}

Kotlin

class Solution {
  fun preOrder(root: TreeNode?): List<Int> {
    return buildPreOrder(root, ArrayList())
  }

  private fun buildPreOrder(node: TreeNode?, result: MutableList<Int>): List<Int> {
    if (node != null) {
      result.add(node.data)
      buildPreOrder(node.left, result)
      buildPreOrder(node.right, result)
    }
    return result
  }
}

Swift

class Solution {
    func preOrder(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        return buildPreOrder(root, &result)
    }

    private func buildPreOrder(_ node: TreeNode?, _ result: inout [Int]) -> [Int] {
        if node != nil {
            result.append(node!.data)
            let _ = buildPreOrder(node!.left, &result)
            let _ = buildPreOrder(node!.right, &result)
        }
        return result
    }
}

Ruby

class Solution
  def pre_order(root)
    build_pre_order(root, [])
  end

  def build_pre_order(node, result)
    unless node.nil?
      result << node.data
      build_pre_order(node.left, result)
      build_pre_order(node.right, result)
    end
    result
  end
end

Rust

impl Solution {
    pub fn pre_order(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        let mut result = Vec::new();
        Self::build_pre_order(&root, &mut result);
        result
    }

    fn build_pre_order(node: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
        if let Some(n) = node {
            result.push(n.data);
            Self::build_pre_order(&n.left, result);
            Self::build_pre_order(&n.right, result);
        }
    }
}

C#

public class Solution {
    public List<int> preOrder(TreeNode? root) {
        return BuildPreOrder(root, new List<int>());
    }

    private List<int> BuildPreOrder(TreeNode? node, List<int> result) {
        if (node != null) {
            result.Add(node.data);
            BuildPreOrder(node.left, result);
            BuildPreOrder(node.right, result);
        }
        return result;
    }
}

Dart

class Solution {
  List<int> preOrder(TreeNode? root) {
    return buildPreOrder(root, []);
  }

  List<int> buildPreOrder(TreeNode? node, List<int> result) {
    if (node != null) {
      result.add(node.data);
      buildPreOrder(node.left, result);
      buildPreOrder(node.right, result);
    }
    return result;
  }
}

PHP

class Solution {
    public function preOrder(?TreeNode $root): array {
        return $this->buildPreOrder($root, []);
    }

    private function buildPreOrder(?TreeNode $node, array $result): array {
        if ($node !== null) {
            $result[] = $node->data;
            $result = $this->buildPreOrder($node->left, $result);
            $result = $this->buildPreOrder($node->right, $result);
        }
        return $result;
    }
}