# 6.4 Tree Traversals

> Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.

Chapter: Trees · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/tree-traversals

## Mental model

You are visiting every room in a building. **Depth-first** means you go down one corridor to the end before trying the next. **Breadth-first** means you visit every room on floor 1 before going to floor 2.

### The three depth-first orders

All three go **left before right**. They differ only in **when you visit the node itself**:

| Order | Rule | Memory trick |
| --- | --- | --- |
| **Preorder** | **N**ode, Left, Right | node comes **pre** (before) |
| **Inorder** | Left, **N**ode, Right | node is **in** the middle |
| **Postorder** | Left, Right, **N**ode | node comes **post** (after) |

```cpp
void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    cout << r->data << " ";
    inorder(r->right);
}
```

Move the `cout` line up for preorder, down for postorder.

### What each is good for

- **Preorder**: copying a tree, printing folder structures.
- **Inorder**: a BST in **sorted order**.
- **Postorder**: deleting a tree (children before parent), evaluating expression trees.

### Level order (breadth-first)

Use a **queue**: push the root; repeatedly pop a node, print it, push its left and right children. The queue makes sure nodes come out level by level, left to right. This is BFS, which you will meet again on graphs in Chapter 7.

## C++ code: traversals.cpp

```cpp
#include <iostream>
#include <queue>
using namespace std;

struct Node { int data; Node* left; Node* right; };

Node* insert(Node* r, int x) {
    if (!r) return new Node{x, nullptr, nullptr};
    if (x < r->data) r->left = insert(r->left, x);
    else r->right = insert(r->right, x);
    return r;
}

void preorder(Node* r)  { if (!r) return; cout << r->data << " "; preorder(r->left); preorder(r->right); }
void inorder(Node* r)   { if (!r) return; inorder(r->left); cout << r->data << " "; inorder(r->right); }
void postorder(Node* r) { if (!r) return; postorder(r->left); postorder(r->right); cout << r->data << " "; }

void levelOrder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        cout << cur->data << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }   // postorder!

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, x);
    cout << "preorder:    "; preorder(root);   cout << "\n";
    cout << "inorder:     "; inorder(root);    cout << "\n";
    cout << "postorder:   "; postorder(root);  cout << "\n";
    cout << "level order: "; levelOrder(root); cout << "\n";
    destroy(root);
}
```

Expected output:

```text
preorder:    50 30 20 40 70 60 80 
inorder:     20 30 40 50 60 70 80 
postorder:   20 40 30 60 80 70 50 
level order: 50 30 70 20 40 60 80
```

## Complexity

| Case | Cost |
| --- | --- |
| pre / in / post order | O(n): every node once |
| level order | O(n) |

Space: O(h) recursion for DFS; O(w) queue for level order (w = widest level)

All four visit every node exactly once. They only differ in **when** a node is printed.

## Videos

- [Binary tree traversal: Preorder, Inorder, Postorder](https://youtu.be/gm8DUJJhmY4) (mycodeschool): Preorder, inorder, postorder with recursion, traced on a real tree.
- [Binary tree: Level Order Traversal](https://youtu.be/86g8jAQug04) (mycodeschool): Level order with a queue. This is the same idea as BFS in Chapter 7.

## Exam lens

Likely questions:

- Give the preorder, inorder, postorder and level-order traversals of a drawn tree.
- Write recursive functions for preorder, inorder and postorder.
- Which traversal of a BST gives sorted output?
- Which data structure does level-order traversal use, and why?
- Given preorder and inorder sequences, rebuild the tree.

Common mistakes:

- Mixing the orders. Remember where the **N**ode goes - **pre** = N L R, **in** = L N R, **post** = L R N.
- Forgetting that "left before right" is the same in all three.
- Using a stack for level order (that gives a DFS order instead).

## Quick check

1. Tree: root 1, left 2 (children 4, 5), right 3. Preorder?
   A. 1 2 4 5 3
   B. 4 2 5 1 3
   C. 4 5 2 3 1
   D. 1 2 3 4 5
   Answer: A. Node, then the whole left subtree (2 4 5), then right (3).

2. Same tree. Postorder?
   A. 1 2 4 5 3
   B. 4 2 5 1 3
   C. 4 5 2 3 1
   D. 1 3 2 5 4
   Answer: C. Left subtree (4 5 2), right subtree (3), then root (1).

3. Same tree. Level order?
   A. 1 2 4 5 3
   B. 1 2 3 4 5
   C. 4 5 2 3 1
   D. 4 2 5 1 3
   Answer: B. Level 0 → 1; level 1 → 2 3; level 2 → 4 5.

4. Which traversal would you use to delete every node of a tree safely?
   A. preorder
   B. inorder
   C. postorder
   D. any of them
   Answer: C. Postorder frees both children before the parent, so you never use a freed pointer.

## Practice

**Trace by hand.** Using the BST from 50, 30, 70, 20, 40, 60, 80, 35: write all four traversals.

Solution:

- Preorder: `50 30 20 40 35 70 60 80`
- Inorder: `20 30 35 40 50 60 70 80` (sorted)
- Postorder: `20 35 40 30 60 80 70 50`
- Level order: `50 30 70 20 40 60 80 35`


**Implement it.** Rebuild a tree from preorder `A B D E C F` and inorder `D B E A F C`, then write its postorder.

Hint: The first preorder item is the root. Find it in the inorder list; everything to its left is the left subtree. Repeat.

Root A. Inorder left `D B E`, right `F C`. Left root B (children D, E). Right root C (left child F).

Postorder: `D E B F C A`


**Problems:**

- [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) (easy). Hint: Recursive first. Then try it with an explicit stack.
- [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) (easy). Hint: Same template, print before recursing.
- [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) (medium). Hint: Inside the queue loop, process `q.size()` nodes at a time. That batch is one level.

## Mastery checklist

- [ ] I can write all four traversals of a tree by hand.
- [ ] I can write recursive pre/in/postorder from memory.
- [ ] I can write level order with a queue.
- [ ] I know inorder of a BST is sorted.