Traversing tree with recursion works strange (JavaScript)

Question

I've started to dig into the Tree's theme. And I've found strange (for me) behaviour.

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
    else return 0
  }
}

So, here I've created a node structure, which gets an integer array, and splits it in half till leaves will not contain only one element of the array.

let n_array = [1,3,2,5];
root_node = new tree_node(n_array); 

Now I want to walk through the tree and alert the "n_array" of every node. I've supposed that it should be like this

function show_tree(root_node){
  if (root_node.descendants.lenght != 0){
    root_node.descendants.forEach(element => {
      return show_tree(element);
    });
  }
  else {
    alert(root_node.n_array)
    return 0;
  } 
}

But it doesn't work. If I use a web browser console then root.descendants.length gives me the length. But in my recursion, it doesn't. Every time it's undefined

I've cut more and more from the code and finally, I've got this.

function show_tree(root_node){
  alert(root_node.n_array)
  root_node.descendants.forEach(element => {
    return show_tree(element);
  });  
}

The working solution works, but I don't understand why. I expect that it will run into an error, because at the end of the tree root_node.descendants will be undefined.

And what's even worse - I don't understand why this recursion stops and does not go into an endless loop if in every call root_node.descendants !=0 ... Please help me to understand

1. Why my first version of show_tree doesn't work
2. Why the last one is working.

Answer 1

You have effectively built a tree structure that looks something like so:

    [1, 3, 2, 5]
      /       \
  [1, 3]     [2, 5]
   /   \      /   \
  [1]  [3]   [2]   [5] 
   |    |     |     |
  [ ]  [ ]   [ ]   [ ]

In your first function, you have a few issues. The immediate issue is that you are using .lenght and not .length. The next thing to notice about your function is when it is performing its alert()s. In your case, you're only performing an alert() when a node has an empty array as its descendants property. In the above tree diagram, you'll notice that's only the case for your last nodes [1], [3], [2], and [5], so these are alerted. All other nodes that you traverse do have non-empty descendants, so those are not alerted/logged to the screen:

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
  }
}

let n_array = [1,3,2,5];
root_node = new tree_node(n_array); 

function show_tree(root_node){
  if (root_node.descendants.length != 0){
    root_node.descendants.forEach(element => {
      show_tree(element);
    });
  }
  else {
    console.log(root_node.n_array); // replaced with console.log (as this is a more preferred way of logging data)
  } 
}

show_tree(root_node);
// Logs:
// [1]
// [3]
// [2]
// [5]

Unlike your first function, your second function alerts every node it visits, not just those without descendants. That's because your alert() is the first line of the function, so it will always run the alert for every node that the show_tree() function is called with.

I expect that it will run into an error, because at the end of the tree root_node.descendants will be undefined

If you look at your tree_node class, you'll notice that every node that you create gets a descendants property that gets assigned to an empty array within your constructor. As a result, when you traverse/loop over your tree and make further recursive calls, each node you pass into your show_tree() function will have a descendants property - just sometimes the descendants of a node will be an empty array. As a result, no error occurs when you use:

root_node.descendants.forEach(..)

as it is valid to call .forEach() on an empty array ([]). This leads to your other question...:

I don't understand why this recursion stops and does not go into an endless loop

as you traverse your nodes in your tree, you'll eventually reach your leaf nodes (nodes with no descendants (.descendants is an empty array)). When this occurs, your .forEach() loop won't run the code within its "callback", and so no further recursive calls to show_tree() are made. Instead, the function returns to its caller, which can begin to "unravel" the recursive calls or continue looping over other sibling nodes.

Answer 2

I believe the answers to your questions are:

1. There's a typo in the line root_node.descendants.lenght != 0, we can change this to root_node.descendants.length != 0

2. root_node.descendants won't be undefined, it will be [], or an empty array, so the forEach simply won't run, which is probably the desired behaviour.

I've modified your methods slightly, including a v1 and v2 suffix to differentiate them, and added a depth argument, so we can log the node depth. Also, instead of using alert(), we'll just use console.log().

Running each works now I think, the v1 method will log the leaf nodes only, while the v2 method will log all nodes.

class tree_node {
  constructor(n_array) {
    this.n_array = n_array;
    this.descendants = [];
    this.child();
  }
  child() {
    if (this.n_array.length !=1){
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0,m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l);
      const right = new tree_node(r);
      this.descendants.push(left, right);
    }
    else return 0
  }
}

function show_tree_v1(root_node, depth = 0) {
  if (root_node.descendants.length != 0){
    root_node.descendants.forEach(element => {
      return show_tree_v1(element, depth + 1);
    });
  } else {
    console.log('show_tree_v1: [', root_node.n_array.join(","), '] , depth:', depth)
    return 0;
  } 
}

function show_tree_v2(root_node, depth = 0){
  console.log('show_tree_v2: n_array: [', root_node.n_array.join(","), '], depth:', depth)
  root_node.descendants.forEach(element => {
    return show_tree_v2(element, depth + 1);
  });  
}

let n_array = [1,3,2,5];
root_node = new tree_node(n_array);

console.log('Show tree (v1):')
show_tree_v1(root_node)

console.log('Show tree (v2):')
show_tree_v2(root_node)

.as-console-wrapper { max-height: 100% !important; top: 0; }