JavaScript implementation of printing left view of binary tree is returning incorrect result

Question

I am trying to print the left view of a binary tree as seen here on geeksforgeeks. For some reason it isn't working, I suspect it has to do with max_level. The result is [ 12, 10, 30, 25, 40 ] and I'm expecting [12,10,25].

JS Code

var Node = function(val) {
    this.val = val;
    this.left = this.right = null;
};

var leftViewUtil = function(root, level, max, result) {
    if (root === null) return;

    if (max.level < level) {
        max.level = level;
        result.arr.push(root.val);
    }

    leftViewUtil(root.left, ++level, max, result);
    leftViewUtil(root.right, ++level, max, result);
};

var leftView = function(root) {
    var result = {
        arr: []
    };

    var max_level = {level: 0};

    leftViewUtil(root, 1, max_level, result);

    return result.arr;
};

root = new Node(12);
root.left = new Node(10);
root.right = new Node(30);
root.right.left = new Node(25);
root.right.right = new Node(40);

var run = function() {
    console.log(leftView(root));
};

run();

When you're translating code you shouldn't remove the comments :-) — Bergi
– Bergi, Commented Dec 22, 2015 at 1:13
coding practice from Facebook interview prep, number of visible nodes — xinthose
– xinthose, Commented Apr 6, 2020 at 2:46

Bergi · Accepted Answer · 2015-12-22 01:16:50Z

1

The difference between the code on the linked page is

// Recur for left and right subtrees
leftViewUtil(root->left, level+1, max_level);
leftViewUtil(root->right, level+1, max_level);

vs

leftViewUtil(root.left, ++level, max, result);
leftViewUtil(root.right, ++level, max, result);

You are increasing level twice here, while you should pass the same value to both recursive calls. Either use level+1 as proper, or do the increment before the calls:

++level;
leftViewUtil(root.left, level, max, result);
leftViewUtil(root.right, level, max, result);

answered Dec 22, 2015 at 1:16

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

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

Comments

Chandan Kumar · Accepted Answer · 2020-01-19 11:14:46Z

Using Hash table find left and right view of tree in few lines of code.

right_view(root,num, result) {
    if(root == null) {
        return 0
    }
    right_view(root.Left, num+1, result)
    right_view(root.Right, num+1, result)
    result[num] = root.Value
}

left_view(root,num, result) {
    if(root == null) {
        return 0
    }
    left_view(root.Left, num+1, result)
    left_view(root.Right, num+1, result)
    if(result[num] == undefined) {
        result[num] = root.Value
    }
}

Calling function with root node.

right_view_result = {}
right_view(root,1,right_view_result)
console.log(right_view_result)

Calling function with root node.

left_view_result = {}
left_view(root,1,left_view_result)
console.log(left_view_result)

Collectives™ on Stack Overflow

JavaScript implementation of printing left view of binary tree is returning incorrect result

JS Code

2 Answers 2

Comments

Calling function with root node.

Calling function with root node.

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

JS Code

2 Answers 2

Comments

Calling function with root node.

Calling function with root node.

Comments

Your Answer

Sign up or log in

Post as a guest

Related