Maximum sum of nodes in Binary tree such that no two are adjacent | Java program to find maximum sum from a subset of nodes of binary tree ; A binary tree node structure ; method returns maximum sum possible from subtrees rooted at grandChildrens of node ' node ' ; call for children of left child only if it is not NULL ; call for children of right child only if it is not NULL ; Utility method to return maximum sum rooted at node ' node ' ; If node is already processed then return calculated value from map ; take current node value and call for all grand children ; don 't take current node value and call for all children ; choose maximum from both above calls and store that in map ; Returns maximum sum from subset of nodes of binary tree under given constraints ; Driver code to test above methods
import java . util . HashMap ; public class FindSumOfNotAdjacentNodes { class Node { int data ; Node left , right ; Node ( int data ) { this . data = data ; left = right = null ; } } ; public static int sumOfGrandChildren ( Node node , HashMap < Node , Integer > mp ) { int sum = 0 ; if ( node . left != null ) sum += getMaxSumUtil ( node . left . left , mp ) + getMaxSumUtil ( node . left . right , mp ) ; if ( node . right != null ) sum += getMaxSumUtil ( node . right . left , mp ) + getMaxSumUtil ( node . right . right , mp ) ; return sum ; } public static int getMaxSumUtil ( Node node , HashMap < Node , Integer > mp ) { if ( node == null ) return 0 ; if ( mp . containsKey ( node ) ) return mp . get ( node ) ; int incl = node . data + sumOfGrandChildren ( node , mp ) ; int excl = getMaxSumUtil ( node . left , mp ) + getMaxSumUtil ( node . right , mp ) ; mp . put ( node , Math . max ( incl , excl ) ) ; return mp . get ( node ) ; } public static int getMaxSum ( Node node ) { if ( node == null ) return 0 ; HashMap < Node , Integer > mp = new HashMap < > ( ) ; return getMaxSumUtil ( node , mp ) ; } public static void main ( String args [ ] ) { Node root = new Node ( 1 ) ; root . left = new Node ( 2 ) ; root . right = new Node ( 3 ) ; root . right . left = new Node ( 4 ) ; root . right . right = new Node ( 5 ) ; root . left . left = new Node ( 1 ) ; System . out . print ( getMaxSum ( root ) ) ; } }