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?

raina77ow · Accepted Answer · 2021-06-20 06:16:52Z

2

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.

edited Jun 20, 2021 at 6:16

answered Jun 20, 2021 at 6:05

raina77ow

107k16 gold badges205 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

rudehlabya Over a year ago

For some reason I get an error saying this.dfsInOrder is not an iterable when I use the spread operator

raina77ow Over a year ago

Are you sure you didn't leave those empty return statements?

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related