Given a binary tree, find the maximum sum from root to leaf. The condition is that only the parent or the child can be included in the sum i.e. no two level adjacent nodes will be included in the sum

Question

Accepted Answer

The maximum sum from root to leaf in a binary tree, where only parent or child can be included in the sum.

Use a recursive approach to traverse the binary tree.
At each node, calculate the maximum sum from its left and right child.
Compare the sums and return the maximum sum plus the value of the current node.
Repeat this process until reaching a leaf node.
Track the maximum sum encountered during the traversal.

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

}

Given a binary tree, find the maximum sum from root to leaf. The condition is that only the parent or the child can be included in the sum i.e. no two level adjacent nodes will be included in the sum

Popular interview questions of Software Engineer Intern

Top HR questions asked in Intel Software Engineer Intern