Trees

Question 1

Given a binary tree, modify each node value to be the sum of itself and its parent node.
Return the root node of the modified tree.

Function Signature
createParentSumTree(root)

Expected Runtime
O(n), where n = # of nodes in tree

Examples
[1, 2, 4] => [1, 3, 5]
[1, 3, 4, 3, null, null, null] => [1, 4, 5, 6, null, null, null]
[9] => [9]
[1, 2, 4] => [1, 3, 5]
[1, 3, 4, 3, null, null, null] => [1, 4, 5, 6, null, null, null]
[9] => [9]

Answer 1

const createParentSumTree = (root) => {
  helper(root);
  return root;
}

const helper = (node, parentValue) => {
  if (!node) return;

helper(node.left, node.value);
helper(node.right, node.value);

if (parentValue) {
node.value = node.value + parentValue;
}
}

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

/* Example tree */
const testTree = new TreeNode(9, new TreeNode(3, new TreeNode(1), new TreeNode(5)), new TreeNode(11, new TreeNode(10)))

Question 2

Given a binary tree, return the sum of all nodes with an even-valued parent node.

Function Signature
sumNodesWithEvenParent(root)

Expected Runtime
O(n), where n = # of nodes in tree

Examples
[6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5] => 28
[2, 5, 9] => 14
[2] => 0
[6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5] => 28
[2, 5, 9] => 14
[2] => 0

Expected Questions
If you were presented this question in an interview, these are some questions(s) you might want to ask:
1) Is the root node considered a parent of itself? No.

Answer 2

/*Approach: Initialise sum = 0 and perform a recursive traversal of the tree and check if the node is even or 
  not, if the node is even then add the values of its children to the sum. Finally, print the sum.
*/

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

var res = 0;

const sumNodesWithEvenParent= (root) => {
  //Initialize result
 res = 0;

calcSum(root);
return res;

}

const calcSum = (root) => {
  //Base case - what is it contributing to end result?
  if(root === null) return;

  //if value of current node is even
  if(root.value % 2 == 0){

//if the left child or the right child of the even node exists, then add to result
if(root.left !== null) res += root.left.value;
if(root.right !== null) res += root.right.value;

}

//Visiting the left subtree and the right subtree
calcSum(root.left);
calcSum(root.right);

}

const testTree = new TreeNode(9, new TreeNode(2, new TreeNode(1), new TreeNode(5)), new TreeNode(11, new TreeNode(10)))

console.log(sumNodesWithEvenParent(testTree));

Question 3

We’re given a tree, and we want to find all of the nodes in the tree that are only children (meaning, they are the only child to their parent node).
Return an array of nodes representing each only child in any order.

Function Signature
findOnlyChildren(root): []

Expected Runtime
O(n), where n = # of nodes in tree

Examples
[1, 2, 3, null, 4] => [4]
[12, 3, 4, 1, null, 6, null] => [1, 6]
N/A

Expected Questions
If you were presented this question in an interview, these are some questions(s) you might want to ask:
1) Can our tree be null/empty? Yes.
2) Can there be no child/lonely nodes? Yes.

Answer 3

/*
Create a result array
When you find a node (parent) with a left node/no right node - append the left and continue to DFS.
When you find the opposite, append the right and continue to DFS.
Return result array

*/

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

let res = [];

const findOnlyChildren = (root) => {
  //Initialize result
  res = [];

helper(root);
return res;

}

const helper = (root) => {
  //Base case - what is it contributing to end result?
  if(root === null) return;

  //if parent contains left node but no right node, append the left
  if(root.left && root.right === null){
    res.push(root.left.value)
  }

  //finding the opposite, append the right
  if(root.right && root.left === null) {
    res.push(root.right.value);
  }

//Visiting the left subtree and the right subtree
helper(root.left);
helper(root.right);

}

const testTree = new TreeNode(9, new TreeNode(2, new TreeNode(1), new TreeNode(5)), new TreeNode(11, new TreeNode(10)))

console.log(findOnlyChildren(testTree));