Maximum sum of nodes in Binary tree such that no two are adjacent | C # 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
using System ; public class FindSumOfNotAdjacentNodes { public class Node { public int data ; public Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } ; public static Pair maxSumHelper ( Node root ) { Pair sum ; if ( root == null ) { sum = new Pair ( 0 , 0 ) ; return sum ; } Pair sum1 = maxSumHelper ( root . left ) ; Pair sum2 = maxSumHelper ( root . right ) ; Pair sum3 = new Pair ( 0 , 0 ) ; sum3 . first = sum1 . second + sum2 . second + root . data ; sum3 . second = Math . Max ( sum1 . first , sum1 . second ) + Math . Max ( sum2 . first , sum2 . second ) ; return sum3 ; } public static int maxSum ( Node root ) { Pair res = maxSumHelper ( root ) ; return Math . Max ( res . first , res . second ) ; } public static void Main ( ) { 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 ) ; Console . Write ( maxSum ( root ) ) ; } } public class Pair { public int first , second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } }