console.log Nodes in a Binary Tree who’s subtrees have Even sum

user_16053341 0
Viewed 145

The following is a coding challenge I'm working on.

You are given a binary tree in which each node contains a value. Design an algorithm to print all nodes whose subtree adds up to an even number.

This is the tree I'm working with for testing, together with my function:

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

//       3
//    /    \
//   11     4
//  / \      \
// 4   -2     2

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return;
};

console.log(isEven(a));

The function is not working the way I want it to.

Given this tree, I think the correct output should be: 3, 4, -2, 4 aka a, d, e and c. (assuming null = 0) But the output I'm getting is: 4, -2, 2, undefined

I'm not sure where the 2 is even coming from because no node is equal to 2. (That was a mistake on my part)

tree data-structures binary algorithm javascript
2 Answers

You can make the function return the subtree sum. Then, add the result of calling the function for the left and right children and the value of the node itself to get the sum of the subtree rooted at this node.

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

const checkEven = node => {
  if(!node) return 0;
  const sum = node.val + checkEven(node.left) + checkEven(node.right);
  if(sum % 2 === 0) console.log(node.val);
  return sum;
}
checkEven(a);

user_95131840

the output I'm getting is: 4, -2, 2, undefined.

The reason you get undefined at the end, is that you do a console.log of the main isEven call, but your isEven function returns nothing: its last instruction is return, and so the main console.log outputs undefined. Actually, you should not perform a console.log in your main program, as the printing of nodes is already taken care of in your function.

I'm not sure where the 2 is even coming from because no node is equal to 2.

Node f has a value of 2, and it should be in the output.

I think the correct output should be: 3, 4, -2, 4 aka a, d, e and c. (assuming null = 0)

... and f.

You are not getting all results, because isEven can only return null or undefined, and so left + right will not give what you expect: adding null to a number will treat that null as 0, but when undefined is involved, the expression will evaluate to NaN.

This is solved by changing the final return to return sum.

Here is your script corrected with those two corrections:

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(2);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

//       3
//    /    \
//   11     4
//  / \      \
// 4   -2     2

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return sum; // <-- sum!
};

isEven(a); // <-- no console.log

Alternative tree construction

Not related to your question, but you can make your Node constructor a bit more flexible by defining parameters for specifying left and right references. Then you can build the tree in one, nested expression.

class Node {
  constructor(val, left=null, right=null) {  // <-- extra parameters
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const a = new Node(3,
    new Node(11,
        new Node(4),
        new Node(-2)
    ),
    new Node(4,
        null,
        new Node(2)
    )
);

const isEven = (node) => {
  if (node === null) return 0;
  let left = isEven(node.left);
  let right = isEven(node.right);
  let sum = left + right + node.val;
  if (sum % 2 === 0) {
    console.log(node.val);
  }
  return sum;
};

isEven(a);

user_54598390
Related