Maximum spiral sum in Binary Tree | Java implementation to find maximum spiral sum ; A binary tree node has data , pointer to left child and a pointer to right child ; function to find the maximum sum contiguous subarray . implements kadane 's algorithm  ; to store the maximum value that is ending up to the current index ; to store the maximum value encountered so far ; traverse the array elements ; if max_ending_here < 0 , then it could not possibly contribute to the maximum sum further ; else add the value arr [ i ] to max_ending_here ; update max_so_far ; required maxium sum contiguous subarray value ; Function to find maximum spiral sum ; if tree is empty ; Create two stacks to store alternate levels For levels from right to left ; For levels from left to right ; ArrayList to store spiral order traversal of the binary tree ; Push first level to first stack ' s1' ; traversing tree in spiral form until there are elements in any one of the stacks ; traverse current level from s1 and push nodes of next level to s2 ; push temp - data to ' arr ' ; Note that right is pushed before left ; traverse current level from s2 and push nodes of next level to s1 ; push temp - data to ' arr ' ; Note that left is pushed before right ; required maximum spiral sum ; Driver program to test above
import java . util . ArrayList ; import java . util . Stack ; public class MaxSpiralSum { class Node { int data ; Node left , right ; Node ( int data ) { this . data = data ; left = right = null ; } } ; static int maxSum ( ArrayList < Integer > arr ) { int max_ending_here = Integer . MIN_VALUE ; int max_so_far = Integer . MIN_VALUE ; for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { if ( max_ending_here < 0 ) max_ending_here = arr . get ( i ) ; else max_ending_here += arr . get ( i ) ; max_so_far = Math . max ( max_so_far , max_ending_here ) ; } return max_so_far ; } public static int maxSpiralSum ( Node root ) { if ( root == null ) return 0 ; Stack < Node > s1 = new Stack < > ( ) ; Stack < Node > s2 = new Stack < > ( ) ; ArrayList < Integer > arr = new ArrayList < > ( ) ; s1 . push ( root ) ; while ( ! s1 . isEmpty ( ) || ! s2 . isEmpty ( ) ) { while ( ! s1 . isEmpty ( ) ) { Node temp = s1 . pop ( ) ; arr . add ( temp . data ) ; if ( temp . right != null ) s2 . push ( temp . right ) ; if ( temp . left != null ) s2 . push ( temp . left ) ; } while ( ! s2 . isEmpty ( ) ) { Node temp = s2 . pop ( ) ; arr . add ( temp . data ) ; if ( temp . left != null ) s1 . push ( temp . left ) ; if ( temp . right != null ) s1 . push ( temp . right ) ; } } return maxSum ( arr ) ; } public static void main ( String args [ ] ) { Node root = new Node ( - 2 ) ; root . left = new Node ( - 3 ) ; root . right = new Node ( 4 ) ; root . left . left = new Node ( 5 ) ; root . left . right = new Node ( 1 ) ; root . right . left = new Node ( - 2 ) ; root . right . right = new Node ( - 1 ) ; root . left . left . left = new Node ( - 3 ) ; root . right . right . right = new Node ( 2 ) ; System . out . print ( " Maximum ▁ Spiral ▁ Sum ▁ = ▁ " + maxSpiralSum ( root ) ) ; } }