# Tree Traversal Methods: Preorder, Inorder, Postorder, and Level Order Explained

> Understand preorder inorder postorder and level order tree traversal methods. Learn the unique sequence and use cases for each from serialization to sorted retrieval.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: deep-dive
- Published: 2026-02-25

---

**Tree traversal methods differ in the sequence they visit nodes—preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), and level-order (level by level)—each serving distinct use cases from serialization to sorted retrieval.**

Tree traversal methods form the foundation of binary tree algorithms, determining how you access, process, or transform hierarchical data. In the `krahets/hello-algo` repository, these fundamental algorithms are implemented with clean, educational code that demonstrates the architectural split between depth-first and breadth-first strategies.

## Understanding the Four Tree Traversal Methods

The four classic tree traversal methods differ in **the sequence in which a node, its left subtree, and its right subtree are visited** and in **whether the algorithm follows a depth-first or breadth-first strategy**.

### Preorder Traversal (Root → Left → Right)

**Preorder traversal** visits the current node before its children, following a root-left-right sequence. This method is ideal for **serializing a tree**, **copying a tree structure**, or evaluating prefix expressions because it captures parent nodes before their descendants.

According to the `krahets/hello-algo` source code in [`codes/javascript/chapter_tree/binary_tree_dfs.js`](https://github.com/krahets/hello-algo/blob/main/codes/javascript/chapter_tree/binary_tree_dfs.js), the recursive implementation is:

```javascript
function preOrder(root) {
    if (root === null) return;
    list.push(root.val);  // Visit root
    preOrder(root.left);  // Traverse left subtree
    preOrder(root.right); // Traverse right subtree
}

```

### Inorder Traversal (Left → Root → Right)

**Inorder traversal** visits the left subtree first, then the current node, then the right subtree. For **binary search trees (BSTs)**, this produces values in **ascending sorted order**, making it essential for ordered retrieval operations and validation.

The implementation in [`binary_tree_dfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_dfs.js) follows the same recursive pattern:

```javascript
function inOrder(root) {
    if (root === null) return;
    inOrder(root.left);   // Traverse left subtree
    list.push(root.val);  // Visit root
    inOrder(root.right); // Traverse right subtree
}

```

### Postorder Traversal (Left → Right → Root)

**Postorder traversal** visits children before their parent, processing left-right-root. This is critical for **deleting trees** (ensuring children are freed before their parents), **evaluating postfix expressions**, and computing **subtree sizes** or properties that depend on children results.

From [`binary_tree_dfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_dfs.js):

```javascript
function postOrder(root) {
    if (root === null) return;
    postOrder(root.left);  // Traverse left subtree
    postOrder(root.right); // Traverse right subtree
    list.push(root.val);   // Visit root
}

```

### Level Order Traversal (Breadth-First)

**Level order traversal** visits nodes level by level, left-to-right within each level, using a **breadth-first search (BFS)** strategy. Unlike the depth-first methods, it uses an **explicit queue** rather than the call stack, making it optimal for **shortest-path problems** on trees and **level-by-level printing**.

The implementation in [`codes/javascript/chapter_tree/binary_tree_bfs.js`](https://github.com/krahets/hello-algo/blob/main/codes/javascript/chapter_tree/binary_tree_bfs.js) demonstrates the queue-based approach:

```javascript
function levelOrder(root) {
    const queue = [root];
    const list = [];
    while (queue.length) {
        const node = queue.shift();
        list.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return list;
}

```

## Practical Code Examples

To run these tree traversal methods, use the utility functions provided in the `krahets/hello-algo` repository. The [`TreeNode.js`](https://github.com/krahets/hello-algo/blob/main/TreeNode.js) module provides `arrToTree` to construct trees from arrays, while [`binary_tree_dfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_dfs.js) and [`binary_tree_bfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_bfs.js) export the traversal functions.

```javascript
// Example: using the traversal utilities
const { arrToTree } = require('./modules/TreeNode');
const { preOrder, inOrder, postOrder } = require('./chapter_tree/binary_tree_dfs');
const { levelOrder } = require('./chapter_tree/binary_tree_bfs');

// Build a complete binary tree from an array representation
const root = arrToTree([1, 2, 3, 4, 5, 6, 7]);

// Depth‑first traversals
let result = [];
preOrder(root);   console.log('Pre‑order :', result);   // → 1,2,4,5,3,6,7
result = []; 
inOrder(root);    console.log('In‑order  :', result);   // → 4,2,5,1,6,3,7
result = []; 
postOrder(root);  console.log('Post‑order:', result);   // → 4,5,2,6,7,3,1

// Breadth‑first traversal
const bfsResult = levelOrder(root);
console.log('Level‑order:', bfsResult);               // → 1,2,3,4,5,6,7

```

**What the code does:**

1. `arrToTree` converts a level‑order array into a linked‑node binary tree (see **[`TreeNode.js`](https://github.com/krahets/hello-algo/blob/main/TreeNode.js)**).
2. `preOrder`, `inOrder`, and `postOrder` recursively push node values into a shared `list` array (defined in **[`binary_tree_dfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_dfs.js)**).
3. `levelOrder` creates a FIFO queue, dequeues nodes level by level, and records their values (see **[`binary_tree_bfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_bfs.js)**).

## Summary

- **Preorder** (root-left-right) uses depth-first search to capture parent nodes before children, ideal for serialization and tree copying.
- **Inorder** (left-root-right) retrieves binary search tree values in ascending sorted order, essential for ordered data retrieval.
- **Postorder** (left-right-root) processes children before parents, required for safe tree deletion and postfix expression evaluation.
- **Level order** traverses nodes level-by-level using a queue-based breadth-first approach, optimal for shortest-path problems and level-wise printing.

## Frequently Asked Questions

### When should I use preorder versus postorder traversal?

Use **preorder traversal** when you need to process a parent node before its children, such as when serializing a tree structure or creating a deep copy where parent initialization must occur first. Use **postorder traversal** when child processing must complete before parent processing, such as when deleting nodes to ensure children are freed before their parents, or when evaluating postfix expressions where operands must be resolved before operators.

### Why does inorder traversal produce sorted output for binary search trees?

**Inorder traversal** visits nodes in the sequence left-root-right. In a **binary search tree (BST)**, all values in the left subtree are smaller than the root, and all values in the right subtree are larger. By recursively visiting the left subtree first (smaller values), then the root (middle value), then the right subtree (larger values), inorder traversal naturally retrieves values in ascending sorted order.

### Is level order traversal always implemented with a queue?

While **level order traversal** is conceptually a breadth-first search that can be implemented with various mechanisms, it is **standard practice to use a queue** (FIFO structure) to achieve the level-by-level behavior. The queue ensures that nodes are processed in the order they are discovered, allowing you to enqueue children of the current level while dequeuing nodes from the previous level. Alternative implementations using recursion and depth tracking exist but are less efficient and more complex than the iterative queue approach used in [`binary_tree_bfs.js`](https://github.com/krahets/hello-algo/blob/main/binary_tree_bfs.js).

### What is the time and space complexity of these tree traversal methods?

All four **tree traversal methods**—preorder, inorder, postorder, and level order—have **O(n) time complexity**, where n is the number of nodes, because each node must be visited exactly once. For space complexity, the **depth-first traversals** (preorder, inorder, postorder) use **O(h)** space, where h is the height of the tree, due to the recursive call stack; this becomes O(n) in the worst case of a skewed tree. The **level order traversal** uses **O(w)** space, where w is the maximum width of the tree, as it stores at most one level in the queue at a time; this also becomes O(n) in the worst case of a complete binary tree's last level.