All tree traversals — inorder, preorder, postorder (recursive & iterative), level order, zig-zag

Easy

Problem

Produce the standard traversals of a binary tree:

Inorder (left, node, right), preorder (node, left, right) and postorder (left, right, node) — both recursively and iteratively with an explicit stack.

Level order (top to bottom), reverse level order, and zig-zag (alternate left→right and right→left on each level).

Example 1

Input:  root = [1, 2, 3, 4, 5]  (2 has children 4, 5)
Output: in: 4 2 5 1 3 · pre: 1 2 4 5 3 · post: 4 5 2 3 1 · zig-zag: [[1], [3, 2], [4, 5]]

Also asked as: Inorder Traversal of a tree both using recursion and Iteration · Preorder Traversal of a tree both using recursion and Iteration · Postorder Traversal of a tree both using recursion and Iteration · Reverse Level Order traversal · Zig-Zag traversal of a binary tree

Test cases

Case 1

Input:    [1,null,2,3]
Expected: [1,3,2]

Case 2

Input:    [1,2,3,4,5]
Expected: [4,2,5,1,3]

Case 3

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution3 approaches

1. Recursive DFS (the three orders)

Time O(n)Space O(h)

Visit the node before / between / after its children for pre / in / post order.

const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
const preorder = (n, out = []) => { if (n) { out.push(n.val); preorder(n.left, out); preorder(n.right, out); } return out; };
const postorder = (n, out = []) => { if (n) { postorder(n.left, out); postorder(n.right, out); out.push(n.val); } return out; };

2. Iterative with an explicit stack

Time O(n)Space O(h)

Preorder: push right then left. Inorder: push all lefts, pop-visit-go-right. Postorder: do a reversed "root-right-left" preorder.

function inorderIter(root) {
const out = [], st = [];
let cur = root;
while (cur || st.length) {
while (cur) { st.push(cur); cur = cur.left; }
cur = st.pop();
out.push(cur.val);
cur = cur.right;
}
return out;
}
function postorderIter(root) {
const out = [], st = root ? [root] : [];
while (st.length) {
const n = st.pop();
out.push(n.val);
if (n.left) st.push(n.left);
if (n.right) st.push(n.right);
}
return out.reverse();
}

3. Level order, reverse level order, zig-zag (BFS)

Time O(n)Space O(width)

BFS one level at a time. Reverse level order: reverse the collected levels (or unshift). Zig-zag: reverse alternate levels.

function zigzag(root) {
if (!root) return [];
const res = [], q = [root];
let leftToRight = true;
while (q.length) {
const level = [];
for (let k = q.length; k > 0; k--) {
const n = q.shift();
level.push(n.val);
if (n.left) q.push(n.left);
if (n.right) q.push(n.right);
}
res.push(leftToRight ? level : level.reverse());
leftToRight = !leftToRight;
}
return res;
}
// reverse level order = build levels normally, then res.reverse()