Maximum sum of nodes in Binary tree such that no two are adjacent | Java program to find maximum sum in Binary Tree such that no two nodes are adjacent . ; A binary tree node structure ; maxSumHelper function ; This node is included ( Left and right children are not included ) ; This node is excluded ( Either left or right child is included ) ; Returns maximum sum from subset of nodes of binary tree under given constraints ; Driver code ; Pair class
public class FindSumOfNotAdjacentNodes { class Node { int data ; Node left , right ; Node ( int data ) { this . data = data ; left = right = null ; } } ; public static Pair maxSumHelper ( Node root ) { if ( root == null ) { Pair sum = new Pair ( 0 , 0 ) ; return sum ; } Pair sum1 = maxSumHelper ( root . left ) ; Pair sum2 = maxSumHelper ( root . right ) ; Pair sum = new Pair ( 0 , 0 ) ; sum . first = sum1 . second + sum2 . second + root . data ; sum . second = Math . max ( sum1 . first , sum1 . second ) + Math . max ( sum2 . first , sum2 . second ) ; return sum ; } public static int maxSum ( Node root ) { Pair res = maxSumHelper ( root ) ; return Math . max ( res . first , res . second ) ; } public static void main ( String args [ ] ) { Node root = new Node ( 10 ) ; root . left = new Node ( 1 ) ; root . left . left = new Node ( 2 ) ; root . left . left . left = new Node ( 1 ) ; root . left . right = new Node ( 3 ) ; root . left . right . left = new Node ( 4 ) ; root . left . right . right = new Node ( 5 ) ; System . out . print ( maxSum ( root ) ) ; } } class Pair { int first , second ; Pair ( int first , int second ) { this . first = first ; this . second = second ; } }