Tree Traversals (Inorder, Preorder, Postorder + Level Order)

A comprehensive guide to all binary tree traversal methods with deep intuition, ASCII art visualizations, recursive and iterative implementations, Morris traversal, tree construction from traversals, and complete C++ solutions for classic problems.

Binary Tree Node
The Example Tree
Inorder Traversal (L -> Root -> R)
Preorder Traversal (Root -> L -> R)
Postorder Traversal (L -> R -> Root)
Level Order Traversal (BFS)
Morris Traversal --- O(1) Space
Summary Table
Constructing Trees from Traversals
Classic Problems with Full Solutions

Binary Tree Node

CPP

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

The Example Tree

We will use this tree throughout the entire document:

Structure:

Root: 1
1's left child: 2, right child: 3
2's left child: 4, right child: 5
3's right child: 6
5's left child: 7
Nodes 4, 7, 6 are leaf nodes

Statistics:

7 nodes total
Height: 3 (longest path from root to leaf: 1 -> 2 -> 5 -> 7)
It is NOT a BST (just a general binary tree)

The Three DFS Traversals

1. Inorder Traversal (Left -> Root -> Right)

Intuition

Visit the left subtree first, then the current node, then the right subtree. If you imagine projecting the tree downward onto a horizontal line, inorder traversal visits nodes from left to right.

Step-by-Step Trace

            1
           / \
          2    3
         / \    \
        4   5    6
           /
          7

Call: inorder(1)
  Call: inorder(2)                         -- go left from 1
    Call: inorder(4)                       -- go left from 2
      Call: inorder(null)                  -- 4 has no left child, return
      VISIT 4                             -- process node 4
      Call: inorder(null)                  -- 4 has no right child, return
    VISIT 2                               -- process node 2
    Call: inorder(5)                       -- go right from 2
      Call: inorder(7)                     -- go left from 5
        Call: inorder(null)                -- 7 has no left child, return
        VISIT 7                            -- process node 7
        Call: inorder(null)                -- 7 has no right child, return
      VISIT 5                             -- process node 5
      Call: inorder(null)                  -- 5 has no right child, return
  VISIT 1                                 -- process node 1
  Call: inorder(3)                         -- go right from 1
    Call: inorder(null)                    -- 3 has no left child, return
    VISIT 3                               -- process node 3
    Call: inorder(6)                       -- go right from 3
      Call: inorder(null)                  -- 6 has no left child, return
      VISIT 6                             -- process node 6
      Call: inorder(null)                  -- 6 has no right child, return

Result: [4, 2, 7, 5, 1, 3, 6]

Visual: Which nodes appear when

Inorder: [4, 2, 7, 5, 1, 3, 6]

Key Property

Inorder traversal of a Binary Search Tree (BST) produces elements in sorted (ascending) order. This is because in a BST, left < root < right, so visiting left first, then root, then right gives a sorted sequence.

Inorder: [2, 3, 4, 5, 6, 7, 8] -- sorted!

This property is the foundation for many BST algorithms:

Validate BST (check if inorder is sorted)
Find kth smallest element
Convert BST to sorted array

Recursive Implementation

CPP

void inorder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);         // L
    result.push_back(root->val);         // Root
    inorder(root->right, result);        // R
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorder(root, result);
    return result;
}

Iterative Implementation (Using Stack)

The key insight: we need to go as far left as possible, then process, then go right. The stack stores nodes we have visited but not yet processed.

Algorithm:
1. Push all left children onto stack (go as far left as possible)
2. Pop a node, process it
3. Move to its right child
4. Repeat

Stack trace for our example tree:

curr = 1: push 1, go left
curr = 2: push 2, go left
curr = 4: push 4, go left
curr = null: stop pushing

Pop 4, process 4.  Output: [4]
  curr = 4->right = null

Pop 2, process 2.  Output: [4, 2]
  curr = 2->right = 5

curr = 5: push 5, go left
curr = 7: push 7, go left
curr = null: stop pushing

Pop 7, process 7.  Output: [4, 2, 7]
  curr = 7->right = null

Pop 5, process 5.  Output: [4, 2, 7, 5]
  curr = 5->right = null

Pop 1, process 1.  Output: [4, 2, 7, 5, 1]
  curr = 1->right = 3

curr = 3: push 3, go left
curr = null: stop pushing

Pop 3, process 3.  Output: [4, 2, 7, 5, 1, 3]
  curr = 3->right = 6

curr = 6: push 6, go left
curr = null: stop pushing

Pop 6, process 6.  Output: [4, 2, 7, 5, 1, 3, 6]
  curr = 6->right = null

Stack empty, curr = null. Done!

CPP

vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr || !st.empty()) {
        // Go as far left as possible
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        // Process the leftmost unprocessed node
        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        // Move to right subtree
        curr = curr->right;
    }
    return result;
}

Time: O(n) --- each node is pushed and popped exactly once. Space: O(h) where h is the height (O(n) worst case for skewed tree, O(log n) for balanced).

2. Preorder Traversal (Root -> Left -> Right)

Intuition

Visit the current node first, then the left subtree, then the right subtree. This is the most natural "top-down" traversal --- you process a node as soon as you arrive at it, before exploring its children.

Think of it as: you're entering a building and writing down each room number as you enter it, before exploring its sub-rooms.

Step-by-Step Trace

            1
           / \
          2    3
         / \    \
        4   5    6
           /
          7

VISIT 1
  VISIT 2                    -- left of 1
    VISIT 4                  -- left of 2
      (null left, null right)
    VISIT 5                  -- right of 2
      VISIT 7               -- left of 5
        (null left, null right)
      (null right)
  VISIT 3                    -- right of 1
    (null left)
    VISIT 6                  -- right of 3
      (null left, null right)

Result: [1, 2, 4, 5, 7, 3, 6]

Visual

Preorder: [1, 2, 4, 5, 7, 3, 6]

Key Properties

The first element is always the root of the tree/subtree.
Preorder is used to serialize (save) a tree --- you can reconstruct the tree from preorder + one additional traversal.
Preorder corresponds to the order you would visit nodes doing a DFS with "process on entry".

Recursive Implementation

CPP

void preorder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    result.push_back(root->val);           // Root
    preorder(root->left, result);           // L
    preorder(root->right, result);          // R
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    preorder(root, result);
    return result;
}

Iterative Implementation

Simpler than inorder! Push root, then repeatedly pop and push right child first (so left is processed first due to LIFO).

Stack trace:

Push 1.
  Stack: [1]

Pop 1, process 1.  Output: [1]
  Push right(3), then left(2).
  Stack: [3, 2]

Pop 2, process 2.  Output: [1, 2]
  Push right(5), then left(4).
  Stack: [3, 5, 4]

Pop 4, process 4.  Output: [1, 2, 4]
  No children.
  Stack: [3, 5]

Pop 5, process 5.  Output: [1, 2, 4, 5]
  Push right(null), push left(7).
  Stack: [3, 7]

Pop 7, process 7.  Output: [1, 2, 4, 5, 7]
  No children.
  Stack: [3]

Pop 3, process 3.  Output: [1, 2, 4, 5, 7, 3]
  Push right(6), no left.
  Stack: [6]

Pop 6, process 6.  Output: [1, 2, 4, 5, 7, 3, 6]
  No children.
  Stack: []

Done!

CPP

vector<int> preorderIterative(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);

        // Push RIGHT first, so LEFT is processed first (LIFO)
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

3. Postorder Traversal (Left -> Right -> Root)

Intuition

Visit the left subtree, then the right subtree, then the current node last. This is a "bottom-up" traversal --- you process children before their parent.

Think of it as: you can only report on a room after you have fully explored all its sub-rooms.

Step-by-Step Trace

            1
           / \
          2    3
         / \    \
        4   5    6
           /
          7

postorder(4): null, null -> VISIT 4
postorder(7): null, null -> VISIT 7
postorder(5): visited 7, null -> VISIT 5
postorder(2): visited 4, visited 5 -> VISIT 2
postorder(6): null, null -> VISIT 6
postorder(3): null, visited 6 -> VISIT 3
postorder(1): visited 2, visited 3 -> VISIT 1

Result: [4, 7, 5, 2, 6, 3, 1]

Visual

Postorder: [4, 7, 5, 2, 6, 3, 1]

Key Properties

The last element is always the root of the tree.
Used for deleting/freeing a tree (delete children before parent).
Used for evaluating expression trees (evaluate operands before operator).
Used for calculating subtree properties (e.g., subtree size, height) in bottom-up fashion.
Postorder corresponds to DFS with "process on exit".

Recursive Implementation

CPP

void postorder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    postorder(root->left, result);          // L
    postorder(root->right, result);         // R
    result.push_back(root->val);            // Root
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    postorder(root, result);
    return result;
}

Iterative Implementation

Postorder is the trickiest to do iteratively. There are several approaches:

Method 1: Modified Preorder + Reverse

Observation: Postorder is L, R, Root. If we do a "modified preorder" of Root, R, L (swap left and right), then reverse, we get L, R, Root = postorder!

Modified preorder (Root, R, L): [1, 3, 6, 2, 5, 7, 4]
Reversed:                       [4, 7, 5, 2, 6, 3, 1]  = postorder!

CPP

vector<int> postorderIterative(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);

        // Push LEFT first (opposite of preorder), so RIGHT is processed first
        if (node->left) st.push(node->left);
        if (node->right) st.push(node->right);
    }

    reverse(result.begin(), result.end());
    return result;
}

Method 2: Single Stack with Last Visited Tracking

This approach does not require reversing and processes nodes in true postorder.

CPP

vector<int> postorderIterativeSingleStack(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;
    TreeNode* lastVisited = nullptr;

    while (curr || !st.empty()) {
        // Go as far left as possible
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }

        TreeNode* top = st.top();

        // If right child exists and hasn't been visited, go right
        if (top->right && top->right != lastVisited) {
            curr = top->right;
        } else {
            // Process this node
            result.push_back(top->val);
            lastVisited = top;
            st.pop();
        }
    }
    return result;
}

How Method 2 works, step by step:

Tree:
        1
       / \
      2    3
     / \    \
    4   5    6
       /
      7

Step  | Stack            | Action                     | Output
------|------------------|----------------------------|--------
1     | [1]              | Push 1, go left            |
2     | [1, 2]           | Push 2, go left            |
3     | [1, 2, 4]        | Push 4, go left (null)     |
4     | [1, 2, 4]        | top=4, no right, VISIT 4   | [4]
5     | [1, 2]           | top=2, right=5 exists      |
6     | [1, 2, 5]        | Push 5, go left            |
7     | [1, 2, 5, 7]     | Push 7, go left (null)     |
8     | [1, 2, 5, 7]     | top=7, no right, VISIT 7   | [4,7]
9     | [1, 2, 5]        | top=5, right=null, VISIT 5 | [4,7,5]
10    | [1, 2]           | top=2, right=5 (visited!)  |
      |                  | VISIT 2                    | [4,7,5,2]
11    | [1]              | top=1, right=3 exists      |
12    | [1, 3]           | Push 3, go left (null)     |
13    | [1, 3]           | top=3, right=6 exists      |
14    | [1, 3, 6]        | Push 6, go left (null)     |
15    | [1, 3, 6]        | top=6, no right, VISIT 6   | [4,7,5,2,6]
16    | [1, 3]           | top=3, right=6 (visited!)  |
      |                  | VISIT 3                    | [4,7,5,2,6,3]
17    | [1]              | top=1, right=3 (visited!)  |
      |                  | VISIT 1                    | [4,7,5,2,6,3,1]

Done! Output: [4, 7, 5, 2, 6, 3, 1]

4. Level Order Traversal (BFS)

Intuition

Visit nodes level by level, from top to bottom, left to right within each level. Uses a queue (BFS), not a stack.

Visual

Result: [[1], [2, 3], [4, 5, 6], [7]] | Flat: [1, 2, 3, 4, 5, 6, 7]

Queue Trace

Queue state after each level:

Initial: queue = [1]

Level 0: Process 1
  Enqueue children: 2, 3
  Queue: [2, 3]
  Level result: [1]

Level 1: Process 2, then 3
  From 2: enqueue 4, 5
  From 3: enqueue 6
  Queue: [4, 5, 6]
  Level result: [2, 3]

Level 2: Process 4, 5, 6
  From 4: no children
  From 5: enqueue 7
  From 6: no children
  Queue: [7]
  Level result: [4, 5, 6]

Level 3: Process 7
  From 7: no children
  Queue: []
  Level result: [7]

Final: [[1], [2, 3], [4, 5, 6], [7]]

Implementation

CPP

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();  // Number of nodes at current level
        vector<int> level;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        result.push_back(level);
    }
    return result;
}

The size = q.size() trick: Before processing a level, we capture the current queue size. This tells us exactly how many nodes belong to the current level. All nodes enqueued during this loop belong to the next level.

Recursive Level Order (DFS approach)

You can also implement level order using DFS by passing the level number:

CPP

void dfsLevel(TreeNode* root, int level, vector<vector<int>>& result) {
    if (!root) return;

    if (level >= (int)result.size()) {
        result.push_back({});  // New level
    }

    result[level].push_back(root->val);
    dfsLevel(root->left, level + 1, result);
    dfsLevel(root->right, level + 1, result);
}

vector<vector<int>> levelOrderDFS(TreeNode* root) {
    vector<vector<int>> result;
    dfsLevel(root, 0, result);
    return result;
}

Time and Space

Approach	Time	Space
BFS (queue)	O(n)	O(w) where w = max width of tree
DFS (recursive)	O(n)	O(h) where h = height

For a complete binary tree: w = n/2, h = log n. BFS uses more space. For a skewed tree: w = 1, h = n. DFS uses more space.

Morris Traversal --- O(1) Space!

The Problem with Standard Approaches

Both recursive and iterative traversals use O(h) space (recursion stack or explicit stack). Can we traverse with O(1) extra space?

The Key Idea: Threaded Binary Tree

Morris traversal temporarily modifies the tree by creating threads --- right pointers from a node's inorder predecessor back to the node itself. These threads act as "breadcrumbs" that allow us to return to a node without a stack.

How Threads Work

The inorder predecessor of node X is the rightmost node in X's left subtree. Its right pointer is normally null (since it's the rightmost). Morris traversal temporarily sets this right pointer to X, creating a thread.

Morris Inorder: Step-by-Step

Tree:
        1
       / \
      2    3
     / \    \
    4   5    6
       /
      7

Algorithm:
  curr = root

  For each node:
    If no left child:
      VISIT curr
      curr = curr->right
    If has left child:
      Find inorder predecessor (rightmost in left subtree)
      If predecessor's right is null:
        Create thread: predecessor->right = curr
        curr = curr->left
      If predecessor's right points to curr (thread exists):
        Remove thread: predecessor->right = null
        VISIT curr
        curr = curr->right

Detailed trace:

Step 1: curr = 1
  Has left child (2).
  Find predecessor: go left to 2, then right to 5.
  5->right is null -> CREATE THREAD: 5->right = 1
  curr = 2

        1 <---------+
       / \           |
      2    3     thread
     / \    \        |
    4   5----+   6
       /
      7

Step 2: curr = 2
  Has left child (4).
  Find predecessor: go left to 4. 4->right is null.
  CREATE THREAD: 4->right = 2
  curr = 4

        1 <---------+
       / \           |
      2    3     thread
     / \    \        |
    4---+  5----+   6
    |  thread   |
    +-->2  /
      7

Step 3: curr = 4
  No left child.
  VISIT 4.  Output: [4]
  curr = 4->right = 2 (follow thread!)

Step 4: curr = 2
  Has left child (4).
  Find predecessor: go left to 4. 4->right = 2 (thread exists!)
  REMOVE THREAD: 4->right = null
  VISIT 2.  Output: [4, 2]
  curr = 2->right = 5

Step 5: curr = 5
  Has left child (7).
  Find predecessor: go left to 7. 7->right is null.
  CREATE THREAD: 7->right = 5
  curr = 7

Step 6: curr = 7
  No left child.
  VISIT 7.  Output: [4, 2, 7]
  curr = 7->right = 5 (follow thread!)

Step 7: curr = 5
  Has left child (7).
  Find predecessor: go left to 7. 7->right = 5 (thread exists!)
  REMOVE THREAD: 7->right = null
  VISIT 5.  Output: [4, 2, 7, 5]
  curr = 5->right = 1 (follow thread!)

Step 8: curr = 1
  Has left child (2).
  Find predecessor: 2 -> 5. 5->right = 1 (thread exists!)
  REMOVE THREAD: 5->right = null
  VISIT 1.  Output: [4, 2, 7, 5, 1]
  curr = 1->right = 3

Step 9: curr = 3
  No left child.
  VISIT 3.  Output: [4, 2, 7, 5, 1, 3]
  curr = 3->right = 6

Step 10: curr = 6
  No left child.
  VISIT 6.  Output: [4, 2, 7, 5, 1, 3, 6]
  curr = 6->right = null

curr is null. Done!
Final: [4, 2, 7, 5, 1, 3, 6]  (correct inorder!)

Morris Inorder C++ Code

CPP

vector<int> morrisInorder(TreeNode* root) {
    vector<int> result;
    TreeNode* curr = root;

    while (curr) {
        if (!curr->left) {
            // No left child: visit and go right
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Find inorder predecessor
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr) {
                pred = pred->right;
            }

            if (!pred->right) {
                // First visit: create thread
                pred->right = curr;
                curr = curr->left;
            } else {
                // Second visit: remove thread, process node
                pred->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

Morris Preorder C++ Code

Almost identical to Morris inorder, but we visit the node when creating the thread (first visit) instead of when removing it (second visit).

CPP

vector<int> morrisPreorder(TreeNode* root) {
    vector<int> result;
    TreeNode* curr = root;

    while (curr) {
        if (!curr->left) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr) {
                pred = pred->right;
            }

            if (!pred->right) {
                result.push_back(curr->val);  // Visit HERE (before going left)
                pred->right = curr;
                curr = curr->left;
            } else {
                pred->right = nullptr;
                // Don't visit here (already visited on first encounter)
                curr = curr->right;
            }
        }
    }
    return result;
}

Morris Traversal Complexity

Aspect	Value	Explanation
Time	O(n)	Each edge traversed at most 3 times (twice for finding predecessor, once for following thread)
Space	O(1)	No stack, no recursion, only a few pointers
Modifies tree?	Temporarily yes, but restored to original

When to use Morris traversal: When O(1) space is required and you are allowed to temporarily modify the tree (e.g., you own the tree in memory).

Summary Table

Relationships Between Traversals

For a BST, the following identity holds:
  - Inorder gives SORTED order
  - Preorder gives the ORDER OF INSERTION (if tree was built by insertion)

For any binary tree:
  - Preorder + Inorder -> uniquely determines the tree
  - Postorder + Inorder -> uniquely determines the tree
  - Preorder + Postorder -> NOT unique (ambiguous for non-full trees)

Constructing Trees from Traversals

Construct from Preorder + Inorder (LC 105)

The Algorithm

The first element of preorder is always the root.
Find this root in inorder. Everything to its left is the left subtree, everything to its right is the right subtree.
Use the sizes to split the preorder array correspondingly.
Recurse.

Visual Walkthrough

Preorder: [3, 9, 20, 15, 7]
Inorder:  [9, 3, 15, 20, 7]

Step 1: Root = 3 (first in preorder)
  In inorder, 3 is at index 1.
  Left inorder:  [9]           (1 element)
  Right inorder: [15, 20, 7]   (3 elements)

  Left preorder:  [9]           (next 1 element after root)
  Right preorder: [20, 15, 7]   (remaining 3 elements)

        3
       / \
      ?   ?
  [9]    [20, 15, 7] / [15, 20, 7]

Step 2: Left subtree
  Preorder: [9], Inorder: [9]
  Root = 9, no children.

        3
       / \
      9   ?

Step 3: Right subtree
  Preorder: [20, 15, 7], Inorder: [15, 20, 7]
  Root = 20 (first in preorder)
  In inorder, 20 is at index 1.
  Left inorder:  [15]   Right inorder: [7]
  Left preorder: [15]   Right preorder: [7]

        3
       / \
      9   20
         /  \
        15    7

C++ Code

CPP

class Solution {
    unordered_map<int, int> inorderIndex;
    int preIdx;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preIdx = 0;
        for (int i = 0; i < (int)inorder.size(); i++) {
            inorderIndex[inorder[i]] = i;
        }
        return build(preorder, 0, (int)inorder.size() - 1);
    }

private:
    TreeNode* build(vector<int>& preorder, int inLeft, int inRight) {
        if (inLeft > inRight) return nullptr;

        int rootVal = preorder[preIdx++];
        TreeNode* root = new TreeNode(rootVal);

        int inIdx = inorderIndex[rootVal];

        root->left = build(preorder, inLeft, inIdx - 1);
        root->right = build(preorder, inIdx + 1, inRight);

        return root;
    }
};

Time: O(n) with hash map for O(1) lookup in inorder. Space: O(n) for hash map + O(h) recursion stack.

Construct from Postorder + Inorder (LC 106)

Same idea, but the last element of postorder is the root. We build right subtree first (since postorder processes right before root in reverse).

Postorder: [9, 15, 7, 20, 3]
Inorder:   [9, 3, 15, 20, 7]

Root = 3 (last in postorder)
In inorder: left = [9], right = [15, 20, 7]
Build RIGHT first, then LEFT (reverse postorder).

CPP

class Solution {
    unordered_map<int, int> inorderIndex;
    int postIdx;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        postIdx = (int)postorder.size() - 1;
        for (int i = 0; i < (int)inorder.size(); i++) {
            inorderIndex[inorder[i]] = i;
        }
        return build(postorder, 0, (int)inorder.size() - 1);
    }

private:
    TreeNode* build(vector<int>& postorder, int inLeft, int inRight) {
        if (inLeft > inRight) return nullptr;

        int rootVal = postorder[postIdx--];
        TreeNode* root = new TreeNode(rootVal);

        int inIdx = inorderIndex[rootVal];

        // Build RIGHT subtree first! (reverse of preorder approach)
        root->right = build(postorder, inIdx + 1, inRight);
        root->left = build(postorder, inLeft, inIdx - 1);

        return root;
    }
};

Why Preorder + Postorder is NOT Unique

Preorder: [1, 2] | Postorder: [2, 1]

Both have preorder [1,2] and postorder [2,1]. We cannot determine if 2 is a left or right child without inorder information.

Exception: If the tree is a FULL binary tree (every node has 0 or 2 children), then preorder + postorder uniquely determines the tree.

Classic Problems with Full Solutions

1. Binary Tree Inorder Traversal (LC 94)

Both recursive and iterative solutions covered above. Here is the clean final version:

CPP

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* curr = root;

        while (curr || !st.empty()) {
            while (curr) {
                st.push(curr);
                curr = curr->left;
            }
            curr = st.top(); st.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }
        return result;
    }
};

2. Binary Tree Level Order Traversal (LC 102)

CPP

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> result;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

3. Zigzag Level Order Traversal (LC 103)

Level order, but alternate direction each level (left-to-right, then right-to-left).

Result: [[3], [20, 9], [15, 7]]

CPP

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> result;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;

        while (!q.empty()) {
            int size = q.size();
            vector<int> level(size);

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();

                // Determine position based on direction
                int idx = leftToRight ? i : (size - 1 - i);
                level[idx] = node->val;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            result.push_back(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
};

4. Binary Tree Right Side View (LC 199)

Return the values visible when looking at the tree from the right side.

Right side view: [1, 3, 4] (at each level, the rightmost node)

Approach 1: BFS (last node of each level)

CPP

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return {};
        vector<int> result;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                if (i == size - 1) {
                    result.push_back(node->val);  // Last node in level
                }
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return result;
    }
};

Approach 2: DFS (visit right before left, track depth)

CPP

class Solution {
public:
    vector<int> result;

    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return result;
    }

    void dfs(TreeNode* node, int depth) {
        if (!node) return;
        if (depth == (int)result.size()) {
            result.push_back(node->val);  // First node at this depth from right
        }
        dfs(node->right, depth + 1);  // Visit right FIRST
        dfs(node->left, depth + 1);
    }
};

5. Construct Binary Tree from Preorder and Inorder (LC 105)

Already covered in detail above. See "Construct from Preorder + Inorder" section.

6. Serialize and Deserialize Binary Tree (LC 297)

Convert a tree to a string and back. Use preorder traversal with null markers.

Serialized (preorder): "1,2,#,#,3,4,#,#,5,#,#" (# represents null)

CPP

class Codec {
public:
    // Serialize: Preorder traversal with null markers
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + ","
             + serialize(root->left) + ","
             + serialize(root->right);
    }

    // Deserialize: Rebuild from preorder
    TreeNode* deserialize(string data) {
        queue<string> tokens;
        string token;
        istringstream stream(data);
        while (getline(stream, token, ',')) {
            tokens.push(token);
        }
        return build(tokens);
    }

private:
    TreeNode* build(queue<string>& tokens) {
        if (tokens.empty()) return nullptr;

        string val = tokens.front();
        tokens.pop();

        if (val == "#") return nullptr;

        TreeNode* node = new TreeNode(stoi(val));
        node->left = build(tokens);
        node->right = build(tokens);
        return node;
    }
};

Alternative: Level-order serialization

CPP

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "";
        string result;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            if (node) {
                result += to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            } else {
                result += "#,";
            }
        }
        return result;
    }

    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;

        vector<string> tokens;
        string token;
        istringstream stream(data);
        while (getline(stream, token, ',')) {
            if (!token.empty()) tokens.push_back(token);
        }

        if (tokens.empty() || tokens[0] == "#") return nullptr;

        TreeNode* root = new TreeNode(stoi(tokens[0]));
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;

        while (!q.empty() && i < (int)tokens.size()) {
            TreeNode* node = q.front(); q.pop();

            if (i < (int)tokens.size() && tokens[i] != "#") {
                node->left = new TreeNode(stoi(tokens[i]));
                q.push(node->left);
            }
            i++;

            if (i < (int)tokens.size() && tokens[i] != "#") {
                node->right = new TreeNode(stoi(tokens[i]));
                q.push(node->right);
            }
            i++;
        }
        return root;
    }
};

7. Vertical Order Traversal (LC 987)

Assign each node a column (root = 0, left child = col-1, right child = col+1) and a row (root = 0, children = row+1). Report nodes grouped by column, then row, then value.

Result: [[9], [3, 15], [20], [7]]

CPP

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        // {col -> {row -> sorted values}}
        map<int, map<int, multiset<int>>> nodes;

        // BFS with (node, row, col)
        queue<tuple<TreeNode*, int, int>> q;
        q.push({root, 0, 0});

        while (!q.empty()) {
            auto [node, row, col] = q.front(); q.pop();
            nodes[col][row].insert(node->val);

            if (node->left) q.push({node->left, row + 1, col - 1});
            if (node->right) q.push({node->right, row + 1, col + 1});
        }

        vector<vector<int>> result;
        for (auto& [col, rows] : nodes) {
            vector<int> colVals;
            for (auto& [row, vals] : rows) {
                for (int val : vals) {
                    colVals.push_back(val);
                }
            }
            result.push_back(colVals);
        }
        return result;
    }
};

8. Boundary of Binary Tree (LC 545)

Return the boundary of the tree in anti-clockwise order: left boundary + leaves + right boundary (reversed).

Left boundary: [1, 2, 4] (go left, exclude leaves)
Leaves: [4, 8, 9, 6, 7] (all leaves, left to right)
Right boundary: [7, 3, 1] (go right, exclude leaves, reversed)
Left boundary excludes leaves; leaves listed separately; right boundary excludes leaves. Root listed once at start.
Boundary: [1, 2, 4, 8, 9, 6, 7, 3]

CPP

class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        vector<int> result;

        if (!isLeaf(root)) {
            result.push_back(root->val);
        }

        // Left boundary (excluding root and leaves)
        addLeftBoundary(root->left, result);

        // All leaves (left to right)
        addLeaves(root, result);

        // Right boundary (excluding root and leaves, in reverse)
        addRightBoundary(root->right, result);

        return result;
    }

private:
    bool isLeaf(TreeNode* node) {
        return node && !node->left && !node->right;
    }

    void addLeftBoundary(TreeNode* node, vector<int>& result) {
        while (node) {
            if (!isLeaf(node)) {
                result.push_back(node->val);
            }
            node = node->left ? node->left : node->right;
        }
    }

    void addLeaves(TreeNode* node, vector<int>& result) {
        if (!node) return;
        if (isLeaf(node)) {
            result.push_back(node->val);
            return;
        }
        addLeaves(node->left, result);
        addLeaves(node->right, result);
    }

    void addRightBoundary(TreeNode* node, vector<int>& result) {
        vector<int> temp;
        while (node) {
            if (!isLeaf(node)) {
                temp.push_back(node->val);
            }
            node = node->right ? node->right : node->left;
        }
        // Add in reverse order
        for (int i = (int)temp.size() - 1; i >= 0; i--) {
            result.push_back(temp[i]);
        }
    }
};

Additional Important Traversal Variants

Reverse Level Order

Process levels from bottom to top.

CPP

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> result = levelOrder(root);  // Normal level order
    reverse(result.begin(), result.end());
    return result;
}

Left Side View

Same as right side view, but take first node of each level:

CPP

vector<int> leftSideView(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == 0) result.push_back(node->val);  // First node in level
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

Maximum Width of Binary Tree (LC 662)

Width of a level = position of rightmost node - position of leftmost node + 1. Use indexing: root = 1, left child = 2i, right child = 2i+1.

CPP

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int maxWidth = 0;
        queue<pair<TreeNode*, unsigned long long>> q;
        q.push({root, 0});

        while (!q.empty()) {
            int size = q.size();
            unsigned long long minIdx = q.front().second;
            unsigned long long first, last;

            for (int i = 0; i < size; i++) {
                auto [node, idx] = q.front(); q.pop();
                idx -= minIdx;  // Normalize to prevent overflow

                if (i == 0) first = idx;
                if (i == size - 1) last = idx;

                if (node->left) q.push({node->left, 2 * idx});
                if (node->right) q.push({node->right, 2 * idx + 1});
            }
            maxWidth = max(maxWidth, (int)(last - first + 1));
        }
        return maxWidth;
    }
};

Tree Diameter (using DFS Postorder)

The diameter of a tree is the longest path between any two nodes. It passes through the deepest points of some subtree.

Diameter = 3 (path: 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3)

CPP

class Solution {
    int diameter;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        height(root);
        return diameter;
    }

    int height(TreeNode* node) {
        if (!node) return 0;
        int leftH = height(node->left);    // Postorder: compute children first
        int rightH = height(node->right);
        diameter = max(diameter, leftH + rightH);  // Update diameter through this node
        return 1 + max(leftH, rightH);
    }
};

Complexity Summary for All Traversals

Inorder (iterative) O(n) O(h) Explicit stack

Preorder (recursive) O(n) O(h)

Preorder (iterative) O(n) O(h)

Postorder (recursive) O(n) O(h)

Postorder (iterative) O(n) O(h) Two-stack or single-stack

Level order (BFS) O(n) O(w) w = max width (up to n/2)

Morris inorder O(n) O(1) Modifies tree temporarily

Morris preorder O(n) O(1) Modifies tree temporarily

h = height: balanced O(log n), skewed O(n) w = max width: complete O(n/2) = O(n), skewed O(1)

Final Decision Guide: Which Traversal to Use

Need sorted order from BST?
  -> Inorder

Need to serialize / reconstruct tree?
  -> Preorder (or level order)

Need to process children before parent (bottom-up)?
  -> Postorder

Need level-by-level information?
  -> Level order (BFS)

Need O(1) space traversal?
  -> Morris traversal

Need to evaluate expression tree?
  -> Postorder (evaluate operands before operator)

Need to create a copy of the tree?
  -> Preorder (create node, then recurse on children)

Need to delete/free tree memory?
  -> Postorder (delete children before parent)

Need right/left side view?
  -> Level order or DFS with depth tracking

Need zigzag traversal?
  -> Level order with direction flag

Need vertical order?
  -> BFS/DFS with column tracking + ordered map