Given a binary tree, find the maximum sum from root to leaf, where only the parent or the child can be included in the sum (no two level adjacent nodes will be included in the sum).

Question

Accepted Answer

class TreeNode {

int value;

TreeNode left;

TreeNode right;

TreeNode(int value) {

this.value = value;

left = null;

right = null;

}

public class BinaryTreeMaxSum {

public int maxPathSum(TreeNode root) {

if (root == null) {

return 0;

}

int leftSum = maxPathSum(root.left);

int rightSum = maxPathSum(root.right);

int maxSum = root.value + Math.max(leftSum, rightSum);

if (root.left == null && root.right == null) {

return root.value;

}

return maxSum;

}

public static void main(String[] args) {

// Create a binary tree

TreeNode root = new TreeNode(1);

root.left = new TreeNode(2);

root.right = new TreeNode(3);

root.left.left = new TreeNode(4);

root.left.right = new TreeNode(5);

BinaryTreeMaxSum binaryTreeMaxSum = new BinaryTreeMaxSum();

int maxSum = binaryTreeMaxSum.maxPathSum(root);

System.out.println("Maximum sum from root to leaf: " + maxSum);

}

Asked in Intel

Given a binary tree, find the maximum sum from root to leaf, where only the parent or the child can be included in the sum (no two level adjacent nodes will be included in the sum).

Interview Questions Asked to Software Engineer Intern at Other Companies

Top Skill-Based Questions for Intel Software Engineer Intern