🔄 JavaScript Tree Traversal

DFS — Inorder (Left → Root → Right)

Inorder on a BST gives sorted order.

function inorder(root) {
    if (!root) return [];
    return [...inorder(root.left), root.val, ...inorder(root.right)];
}
// [4, 2, 5, 1, 3]

Iterative inorder:

function inorderIterative(root) {
    const result = [], stack = [];
    let curr = root;
    while (curr || stack.length) {
        while (curr) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        result.push(curr.val);
        curr = curr.right;
    }
    return result;
}

Time: O(n) | Space: O(h)

---

DFS — Preorder (Root → Left → Right)

function preorder(root) {
    if (!root) return [];
    return [root.val, ...preorder(root.left), ...preorder(root.right)];
}
// [1, 2, 4, 5, 3]

---

DFS — Postorder (Left → Right → Root)

function postorder(root) {
    if (!root) return [];
    return [...postorder(root.left), ...postorder(root.right), root.val];
}
// [4, 5, 2, 3, 1]

---

BFS — Level-Order Traversal

function levelOrder(root) {
    if (!root) return [];
    const result = [], queue = [root];
    while (queue.length) {
        const size = queue.length, level = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left)  queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
    // [[1], [2, 3], [4, 5]]
}

Time: O(n) | Space: O(w)

---

Zigzag Level-Order

function zigzagLevelOrder(root) {
    if (!root) return [];
    const result = [], queue = [root];
    let ltr = true;
    while (queue.length) {
        const size = queue.length, level = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left)  queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(ltr ? level : level.reverse());
        ltr = !ltr;
    }
    return result;
}

Time: O(n) | Space: O(w)

---

Right Side View

function rightSideView(root) {
    if (!root) return [];
    const result = [], queue = [root];
    while (queue.length) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (i === size - 1) result.push(node.val);
            if (node.left)  queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return result;
}

Time: O(n) | Space: O(w)

---

Pattern Summary