Binary Tree Array

dfs.js

// Binary tree represented as an array
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6

const tree = [1, 2, 3, 4, 5, null, 6];

function dfs(tree) {
    const result = [];
    const stack = [];

    if (tree.length === 0) return result;

    stack.push(0); // Start with the root node index (0)

    while (stack.length > 0) {
        const nodeIndex = stack.pop(); // Pop the top element

        if (nodeIndex >= tree.length || tree[nodeIndex] === null) {
            continue;
        }

        result.push(tree[nodeIndex]);

        const rightChildIndex = 2 * nodeIndex + 2;
        const leftChildIndex = 2 * nodeIndex + 1;

        // Push right child first so that left child is processed first
        if (rightChildIndex < tree.length) {
            stack.push(rightChildIndex);
        }

        if (leftChildIndex < tree.length) {
            stack.push(leftChildIndex);
        }
    }

    return result;
}

// DFS traversal
const dfsResult = dfs(tree);
console.log("DFS:", dfsResult); // Output: [1, 2, 4, 5, 3, 6]