All tree traversals — inorder, preorder, postorder (recursive & iterative), level order, zig-zag
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: []
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()