CODEWITHSUNDEEP
javascript
Jordan
Jordan

Reputation: 529

Unsure how this snippet works

var count = function(tree) {
    var stack = [];
    var count = 0;
    for (var node = tree; node; count++, node = stack.pop()) {
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    return count;
};

The above code works and returns the count of nodes within a binary tree.

I am confused as to how this works. Does var stack = []; not create an empty array?

If so, does node not become 0 when set within the for loop, thus making both if statements return false and not run?

EDIT: I just realised the code node = stack.pop() will not be executed until the end of the loop body. Therefore node until that point will contain the current node passed into the procedure (Beginning with the head node).

Apologies for the mundane question, it's time for bed I think

Upvotes: 0

Views: 64

Answers (3)

Tamara Wijsman
Tamara Wijsman

Reputation: 12348

// Count is a function that takes a binary tree, each node in the binary tree
// has a left and a right child. The tree itself is also such a note, namely
// the root node of the tree. What Count does with this tree is count the
// amount of nodes.
var count = function(tree) {
    // We first create a new stack, which we plan to use for counting.        
    var stack = [];

    // The initial count is zero.
    var count = 0;

    // Initial: We first take the root node.
    // Condition: As long as node exists.
    // Incrementation: We increment count, and take another node of the stack.
    for (var node = tree; node; count++, node = stack.pop()) {
        // For the current node, place it's left and right node on the stack.
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }

    // Remember: Init --> Body --> Incr --> Cond --> Body --> Incr --> Cond ...

    // Now that all nodes have passed through the stack, return the count.
    return count;
};

Let's say the tree is like this:

   1
  / \
 2   3
    / \
   4   5

This is how it goes:

  • The stack is empty and the count is 0.
  • It starts with "1", it adds it children "2" and "3" on the stack.
  • It increases the count (0 -> 1) and takes a node of the stack, that's "2".
  • It continues with "2", it has no children.
  • It increases the count (1 -> 2) and takes a node of the stack, that's "3".
  • It continues with "2", it adds it children "4" and "5" on the stack.
  • It increases the count (2 -> 3) and takes a node of the stack, that's "4".
  • It continues with "4", it has no children.
  • It increases the count (3 -> 4) and takes a node of the stack, that's "5".
  • It continues with "5", it has no children.
  • It increases the count (4 -> 5) and can't take a node of the stack, it stops.
  • The final count 5 gets returned.

Upvotes: 0

Cornstalks
Cornstalks

Reputation: 38238

You can rewrite it as:

var count = function(tree) {
    var stack = [];
    var count = 0;
    var node = tree; // set node to the tree (the tree's root node)
    while (node) { // while the node is not null
        // The way these pushes are done, it's basically doing a depth first search
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
        count++;
        node = stack.pop();
    }
    return count;
};

In other words, node does not become zero when it is run because stack is empty. It is set to tree, not stack. You can see it work here.

Upvotes: 3

Sandeep G B
Sandeep G B

Reputation: 4015

I have provided comments and have created a JS Fiddle. I hope this helps

    var count = function(tree) {
    // Stack is by default empty (empty array)
    var stack = [];

    var count = 0;

    // Initially set node to the tree root. 'node' always points to the item being processed. 
    // Each node can have left and right children. 
    // They can be null as well.
    // Comparison is to check if the 'node' is undefined or null 
    // count is incremented if a left or right children is found. 
    // stack.pop() removes the top most element from the array/stack. 

    for (var node = tree; node; count++, node = stack.pop()) {

      // verify if left child exists, then push. This will add to the count when it is popped.  

      if (node.left) stack.push(node.left);

      // verify if right child exists, then push. This will add to the count when it is popped.

  if (node.right) stack.push(node.right);
    }
    return count;
};

Upvotes: 2

Related Questions