Finding leftmost nodes in every level of a tree

Here's my code to set up tree nodes.

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

Here's my code to find the leftmost node at each tree level.

function findFirstNodes(root) {

    const stack = [root];

    root.level = 0;
    const firsts = [];

    while (stack.length > 0) {

      const curr = stack.pop();

      if (firsts[curr.level]) {

          firsts.push(curr.value);

      };

      if (curr.left) {

          stack.unshift(curr.left);

      };

    };

    return firsts;

};

Here's my test code.

const simpleTree = new TreeNode(4, null, null);
simpleTree.right = new TreeNode(8, null, null);
simpleTree.left = new TreeNode(3, null, null);
simpleTree.right.right = new TreeNode(2, null, null);

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

Yet my result array comes out empty.

I have a general good grasp on the knowledge of how to traverse trees and such, but many of the details are still rusty to me. The code doesn't result in any errors, but the array just comes out empty. I tried console logging the curr variable when the tree is traversed, but I only get the one with 3.

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 ]