javascript binary-tree depth-first-search

Binary Tree - Depth-First Traversal

I want to do a depth-first traversal for this binary tree:

Here's the node structure:

function TreeNode(data){
    this.data = data
    this.left = this.right = []

    this.addLeft = function(node){
        this.left.push(node)
    }

    this.addRight = function(node){
        this.right.push(node)
    }
}

The visit function (just to print out the node data):

function visit(node){
    console.log(node.data)
}

The traverse function:

function traverse(node){
   if(node === null) return

   visit(node)

   //visit left branch
   for(node of node.left) traverse(node)

   //visit right branch
   for(node of node.right) traverse(node)
}

Add the binary tree structure:

let rootNode = new TreeNode(1)
let node_4A = new TreeNode(4)
let node_4B = new TreeNode(4)
let node_4C = new TreeNode(4)
let node_5A = new TreeNode(5)
let node_5B = new TreeNode(5)

//add root node branches
rootNode.addLeft(node_4A)
rootNode.addRight(node_5A)

node_4A.addLeft(node_4B)
node_4A.addRight(node_4C)
node_5A.addRight(node_5B)

The output:

So it correctly prints out the node data, but there's always an additional right-most node that got printed twice (i.e. the last 5). Do you have any idea why it happens?

I'm not too familiar with Javascript call stack, but could the reason be I'm running 2 for loops in a recursive function?

Thank you.

Solution

You take the same object reference for left and right.

this.left = this.right = []

You need independent arrays:

this.left = [];
this.right = [];

For taking the right node, take different names than node for iterating.

function traverse(node) {
    if (!node) return;  // you never have a value of null for a node
    visit(node)

    //visit left branch
    for (let n of node.left) {
        traverse(n);
    }
    //visit right branch
    for (let n of node.right) {
        traverse(n);
    }
}

function TreeNode(data) {
    this.data = data
    this.left = [];
    this.right = [];

    this.addLeft = function (node) {
        this.left.push(node)
    }

    this.addRight = function (node) {
        this.right.push(node)
    }
}

function visit(node) {
    console.log(node.data)
}

function traverse(node) {
    if (!node) return; // you never have a value of null for a node

    visit(node)

    for (let n of node.left) {
        traverse(n);
    }

    for (let n of node.right) {
        traverse(n);
    }
}

let rootNode = new TreeNode(1)
let node_4A = new TreeNode(4)
let node_4B = new TreeNode(4)
let node_4C = new TreeNode(4)
let node_5A = new TreeNode(5)
let node_5B = new TreeNode(5)

//add root node branches
rootNode.addLeft(node_4A)
rootNode.addRight(node_5A)

node_4A.addLeft(node_4B)
node_4A.addRight(node_4C)
node_5A.addRight(node_5B)
traverse(rootNode);