Javascript – How do I fix this code to find the leftmost node at each level of a tree, not just a binary or binary search tree, but any standard tree?

There are a few issues:

• The condition firsts[curr.level] will not be true as firsts is empty. The only place where you would make this array non-empty, is inside this if block, which means it will never happen. firsts will forever remain empty.

• Apparently you want to store the levels of the nodes in the node instances. While this should not be necessary, you only do it for one node: the root node. It gets level 0. No other level values occur in your code, and no other node gets a level assigned to it.

• Your code never accesses a node’s right property, which at first may seem reasonable (as you are looking for leftmost nodes on each level), but the leftmost node on a level might well be the right child of its parent, or its parent might be a right child, …etc. In fact, your test code creates a tree that has only one node at the bottom level (with value 2), and it is a right child. So you cannot exclude right-sided child nodes.

• The title of your question says your input would be a standard tree. Yet, your TreeNode class is designed only for binary trees.

Not a real problem, but naming your array stack is misleading, because you use it as a queue, not a stack.

The idea to approach this with a queue is good. But because unsift has a bad time complexity, I would suggest to use two (nested) loops: one that iterates the nodes in the last level that was already visited, and one that visits all the direct children of those nodes and puts them in a new array: this will have all nodes of the next level. Once that is done, this array can become the source to work with in the outer loop again. This way it is easy to identify the first node on each level.

Here is the suggested code:

class TreeNode {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function findFirstNodes(root) {
    let levelNodes = [root];

    const firsts = [];
    while (levelNodes.length > 0) {
        firsts.push(levelNodes[0].value);
        const nextLevelNodes = [];
        for (const node of levelNodes) {
            if (node.left) nextLevelNodes.push(node.left);
            if (node.right) nextLevelNodes.push(node.right);
        }
        levelNodes = nextLevelNodes;
    }
    return firsts;
}

// Your test case:
const simpleTree = new TreeNode(4,
    new TreeNode(3),
    new TreeNode(8,
        null,
        new TreeNode(2)
    )
);

console.log(findFirstNodes(simpleTree)); // -> [ 4, 3, 2 ]

To do the same for any rooted tree, not just binary trees, you need to define your TreeNode class differently, and stop using left and right.

class TreeNode {
    constructor(value, ...children) {
        this.value = value;
        this.children = children;
    }
}

function findFirstNodes(root) {
    let levelNodes = [root];

    const firsts = [];
    while (levelNodes.length > 0) {
        firsts.push(levelNodes[0].value);
        levelNodes = levelNodes.flatMap(node => node.children);
    }
    return firsts;
}

// Your test case. Note that now the node with value 2 is "just" 
//    THE child, not specifically a "right" child.
const simpleTree = new TreeNode(4,
    new TreeNode(3),
    new TreeNode(8,
        new TreeNode(2)
    )
);

console.log(findFirstNodes(simpleTree)); // -> [ 4, 3, 2 ]