javascript: pushing binary tree values into an array using the recursion method

Question

I am trying to traverse through a binary search tree using in order traversal and the recursion method. My goal is to push each node's value into an array and return it. Here is my code:

  dfsInOrder(node=this.root) {
    let nodes = []
    if(node === null) return 


    nodes.push(this.dfsInOrder(node.left))
    nodes.push(node.val)
    nodes.push(this.dfsInOrder(node.right))
    return nodes
  }

Here is how I am inserting the data into the tree:

binarySearchTree
  .insert(15)
  .insert(20)
  .insert(10)
  .insert(12);

For clarification the root of the tree's value is 15 and both 10 and 12 are on the left side of the tree. 20 is on the right.

I am looking for a result like this:

[12,10,15,20]

But instead I am getting this:

[Array(3), 15, Array(3)].....


[undefined, 10, Array(3)]
15
[undefined, 20, undefined]

Where am I going wrong in my code?

Answer 1

Here's one way to fix this:

dfsInOrder(node=this.root) {
  const nodes = [];

  if (node !== null) {
    nodes.push(
      ...this.dfsInOrder(node.left),
      node.val,
      ...this.dfsInOrder(node.right)
    );
  }

  return nodes;
}

In this code, dfsInOrder...

• always returns a flat array, empty for edges. This is slightly better from type check perspective, but also allows filtering out these undefined values you see now
• always flattens results of recursive calls (by ... operator) when inserting them to the resulting array

As a sidenote, push doesn't change your array reference, so there's no need to use let here. Actually, this function can be rewritten to avoid intermediate variable completely:

dfsInOrder(node=this.root) {
  if (node === null) return [];

  return [
    ...this.dfsInOrder(node.left),
    node.val,
    ...this.dfsInOrder(node.right),
  ];
}

... which is fine by me, but is slightly harder to debug.