JavaScript Binary Search Tree in-order traversal returning undefined as part of answer

Question

I'm writing a recursive in-order traversal method for a BST in JS. The method is supposed to return numerical leaf values in order within an array. So far, my written method does that. But in addition to the in-order numbers, it also returns 3 'undefined' at the end of my array as well. My code for the in order method is here:

this.inorder = function(){
        let travArr = [];

        function recurTrav(node){
            if(node.left == null && node.right == null){
                console.log("leaf: " + node.value);
                return node.value;
            }
            else if(node.right == null){
                console.log("right is null, val: " + node.value);
                travArr.push(recurTrav(node.left));
                travArr.push(node.value);
            }
            else if(node.left == null){
                console.log("left is null, val:" + node.value);
                travArr.push(node.value);
                travArr.push(recurTrav(node.right));
            }
            else{
                console.log("no nulls:");
                travArr.push(recurTrav(node.left));
                travArr.push(node.value);
                travArr.push(recurTrav(node.right));
            }
        }

        recurTrav(this.root);
        return travArr;
}

The this.root is the root node of the BST. I have an add method that I didn't include here, for the sake of simplicity. Nodes have a value, left, and right property.

If I added the numbers 3, 2, 5, 6, 14, 8 to my BST in that order, my .inorder() method returns [2, 3, 5, 6, 8, 14, undefined, undefined, undefined] for some reason. I can't figure out where those 3 undefined's are coming from. I think it might be because of my travArr.push(), which might potentially return 'undefined'.

I realize I could probably just do some array manipulation to take those 'undefined' out, but I really want to understand how I wrote my code wrong in the first place. If including my full code for my BST is easier, just let me know and I'll include it.

Nina Scholz · Accepted Answer · 2018-06-22 11:01:56Z

2

You might have a look to this part:

function recurTrav(node) {
    if (node.left == null && node.right == null){
        console.log("leaf: " + node.value);
        return node.value;                                 // returns a value
    } else if(node.right == null){
        console.log("right is null, val: " + node.value);
        travArr.push(recurTrav(node.left));                // <------ could take undefined
        travArr.push(node.value);                          // no return until end of funct
    }
    //..
    // missing return, takes default return value.
}

Solution: Push only if necessary and call function without using the result for pushing.

function recurTrav(node) {
    if (!node.left && !node.right) {                      // falsy check incl undefined/null
        console.log("leaf: " + node.value);
        travArr.push(node.value);
        return;                                           // omit else parts
    }                                                     // with early returns
    if (!node.right) {
        console.log("right is null, val: " + node.value);
        recurTrav(node.left);
        travArr.push(node.value);
        return;
    }
    if (!node.left) {
        console.log("left is null, val:" + node.value);
        travArr.push(node.value);
        recurTrav(node.right);
        return;
    }
    console.log("no nulls:");
    recurTrav(node.left);
    travArr.push(node.value);
    recurTrav(node.right);
}

edited Jun 22, 2018 at 11:01

answered Jun 22, 2018 at 10:54

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

6 Comments

albert Over a year ago

Hey there again Nina! This totally solved my problem, thanks so much again, you really are a life saver. But again, I'm still pretty confused as to why my original code was adding 3 "undefineds" so randomly? Was it because an Array.push() returns an undefined by default or something? I don't see how it could've been the "return node.value", since that actually returns a value

Nina Scholz Over a year ago

it returns the result of the function (default undefined) in cases of not returning the value.

albert Over a year ago

so it was the "if(node.left == null)" and "if(node.right == null)" blocks that were returning the "undefined"?

Nina Scholz Over a year ago

no, the end of the function returns undefined. it has nothing to do with the check. it is just the standard ending of the (every) function in javascript whichg returns undfined, if not using return with a different value.

Nina Scholz Over a year ago

ad else: it is easier to maintain without chaining else parts.

|

Mulan · Accepted Answer · 2018-06-22 13:50:53Z

Given a simple Node constructor

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

And a simple Tree constructor

class Tree
{ constructor (root)
  { this.root = root
  }

  ...
}

We can implement Tree#inorder without the need to null-check left and right branches individually

inorder ()
{ if (this.root === undefined)
    return []

  else
    return [ ...new Tree (this.root.left).inorder ()
           , this.root.value
           , ...new Tree (this.root.right).inorder ()
           ]
}

Run the complete program below to verify the results in your own browser

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

class Tree
{ constructor (root)
  { this.root = root
  }

  inorder ()
  { if (this.root === undefined)
      return []

    else
      return [ ...new Tree (this.root.left).inorder ()
             , this.root.value
             , ...new Tree (this.root.right).inorder ()
             ]
  }
}

const n =
  new Node 
  ( 3
  , new Node
      ( 2
      , new Node (1)
      , undefined
      )
  , new Node
      ( 6
      , new Node
          ( 4
          , undefined
          , new Node (5)
          )
      , new Node (7)
      )
  )

const t =
  new Tree (n)

console.log (t.inorder ())
// [ 1, 2, 3, 4, 5, 6, 7 ]

Collectives™ on Stack Overflow

JavaScript Binary Search Tree in-order traversal returning undefined as part of answer

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related