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

- 1 answer

Ad

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();
Ad

Answer

Ad

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);
Ad
source: stackoverflow.com
Ad