What is In-order traversal useful for?

For a Binary Search Tree, In-order traversal visits nodes in ascending (sorted) order.

Pre-order vs Post-order?

Pre-order (Root-Left-Right) is great for cloning trees. Post-order (Left-Right-Root) is ideal for deleting trees or evaluating postfix expressions.

What is BFS/Level-order?

Breadth-First Search visits all nodes at one level before moving down to the next, typically using a Queue.

Tree Traversal

Tree traversal is the set of algorithms for visiting every node in a tree data structure.

VISIT

Output so far

Left subtree, then root, then right. On a binary SEARCH tree this comes out sorted.

Visit 10 — position 1 of 7.

Visit 25 — position 2 of 7.

Order

Intuition

Imagine exploring a maze. You can either explore all nearby paths first (BFS) or go as deep as possible down one path before backtracking (DFS).

Concept

Tree traversal is the process of visiting each node in a tree data structure exactly once. BFS uses a Queue to visit nodes level by level. DFS uses a Stack (or recursion) to go deep into branches.

How it Works

BFS (Level Order): Visits nodes level by level (Root, then Level 1, then Level 2...).
DFS Pre-order: Root → Left → Right.
DFS In-order: Left → Root → Right.
DFS Post-order: Left → Right → Root.

Step-by-Step Breakdown

BFS Algorithm:

Push Root to Queue.
While Queue is not empty:
Dequeue node and Visit it.
Enqueue Left child (if exists).
Enqueue Right child (if exists).

When to Use

BFS: Finding shortest path in unweighted graphs/trees. Level-order printing.
DFS: Pathfinding, topological sorting, solving puzzles (mazes).
In-order: Getting sorted elements from a BST.

When NOT to Use

BFS: When tree is very wide (high memory usage for queue).
DFS: When tree is very deep (stack overflow risk).

How to Identify

Keywords: "Level order", "Shortest path" (BFS), "Explore all paths", "Backtracking" (DFS).

AI resume checker — match your resume to the job description

Priority Queue (ADT)

Binary Tree

Complexity

Time (Best)

O(n)

Time (Average)

O(n)

Time (Worst)

O(n)

Space

O(w) or O(h)

Tree Traversal Code

1// BFS - Level Order Traversal
2function levelOrder(root) {
3    if (!root) return [];
4    const result = [];
5    const queue = [root];
6    while (queue.length > 0) {
7        const node = queue.shift();
8        result.push(node.val);
9        if (node.left) queue.push(node.left);
10        if (node.right) queue.push(node.right);
11    }
12    return result;
13}
14
15// DFS - Pre-order Traversal (Root -> Left -> Right)
16function preOrder(root) {
17    if (!root) return [];
18    const result = [];
19    function traverse(node) {
20        if (!node) return;
21        result.push(node.val);
22        traverse(node.left);
23        traverse(node.right);
24    }
25    traverse(root);
26    return result;
27}
28
29// DFS - In-order Traversal (Left -> Root -> Right)
30function inOrder(root) {
31    if (!root) return [];
32    const result = [];
33    function traverse(node) {
34        if (!node) return;
35        traverse(node.left);
36        result.push(node.val);
37        traverse(node.right);
38    }
39    traverse(root);
40    return result;
41}
42
43// DFS - Post-order Traversal (Left -> Right -> Root)
44function postOrder(root) {
45    if (!root) return [];
46    const result = [];
47    function traverse(node) {
48        if (!node) return;
49        traverse(node.left);
50        traverse(node.right);
51        result.push(node.val);
52    }
53    traverse(root);
54    return result;
55}

Related Lessons

Tree Traversal

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Binary Tree Level Order Traversal

Binary Tree Inorder Traversal

Maximum Depth of Binary Tree

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

What is In-order traversal useful for?

Pre-order vs Post-order?

What is BFS/Level-order?