Neel Mishra
← All Posts
DSA Series · Trees · Part 2

Tree Traversals

March 2026 · 8 min read

Overview

Traversals visit every node exactly once. The four fundamental orders:

1 2 3 4 5 6 7

▶ Interactive Traversal Animation

Click a traversal to watch the L‑P‑R tags get crossed out at each node as the algorithm progresses.

Pre-order (Root → Left → Right)

function preorder(node):
if node == null: return visit(node) // process current preorder(node.left) preorder(node.right)

Visit order: 1, 2, 4, 5, 3, 6, 7

Use case: Copying/serialising a tree, prefix expression evaluation.

▶ Pre-order Recursive Call Stack

Watch the recursion stack grow and shrink as pre-order traverses the tree.

1 2 3 4 5 6 7

In-order (Left → Root → Right)

function inorder(node):
if node == null: return inorder(node.left) visit(node) // process current inorder(node.right)

Visit order: 4, 2, 5, 1, 6, 3, 7

Use case: Gives sorted order in a BST. Also for infix expression evaluation.

Post-order (Left → Right → Root)

function postorder(node):
if node == null: return postorder(node.left) postorder(node.right) visit(node) // process current

Visit order: 4, 5, 2, 6, 7, 3, 1

Use case: Deleting a tree (free children before parent), postfix evaluation, calculating directory sizes.

Level-order (BFS)

function levelOrder(root):
queue = [root] while queue is not empty: node = queue.dequeue() visit(node) if node.left: queue.enqueue(node.left) if node.right: queue.enqueue(node.right)

Visit order: 1, 2, 3, 4, 5, 6, 7

Use case: Shortest path in unweighted trees, printing level by level.

▶ Level-order BFS Queue Animation

Watch the queue grow and process nodes level by level.

1 2 3 4 5 6 7

C++ Implementation

#include <queue>
#include <vector>

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

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

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

std::vector<int> levelOrder(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        auto* node = q.front(); q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

Summary