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

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

}