Maximum spiral sum in Binary Tree | C ++ implementation to find maximum spiral sum ; structure of a node of binary tree ; A utility function to create a new node ; 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 ; vector 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } int maxSum ( vector < int > arr , int n ) { int max_ending_here = INT_MIN ; int max_so_far = INT_MIN ; for ( int i = 0 ; i < n ; i ++ ) { if ( max_ending_here < 0 ) max_ending_here = arr [ i ] ; else max_ending_here += arr [ i ] ; max_so_far = max ( max_so_far , max_ending_here ) ; } return max_so_far ; } int maxSpiralSum ( Node * root ) { if ( root == NULL ) return 0 ; stack < Node * > s1 ; stack < Node * > s2 ; vector < int > arr ; s1 . push ( root ) ; while ( ! s1 . empty ( ) || ! s2 . empty ( ) ) { while ( ! s1 . empty ( ) ) { Node * temp = s1 . top ( ) ; s1 . pop ( ) ; arr . push_back ( temp -> data ) ; if ( temp -> right ) s2 . push ( temp -> right ) ; if ( temp -> left ) s2 . push ( temp -> left ) ; } while ( ! s2 . empty ( ) ) { Node * temp = s2 . top ( ) ; s2 . pop ( ) ; arr . push_back ( temp -> data ) ; if ( temp -> left ) s1 . push ( temp -> left ) ; if ( temp -> right ) s1 . push ( temp -> right ) ; } } return maxSum ( arr , arr . size ( ) ) ; } int main ( ) { Node * root = newNode ( -2 ) ; root -> left = newNode ( -3 ) ; root -> right = newNode ( 4 ) ; root -> left -> left = newNode ( 5 ) ; root -> left -> right = newNode ( 1 ) ; root -> right -> left = newNode ( -2 ) ; root -> right -> right = newNode ( -1 ) ; root -> left -> left -> left = newNode ( -3 ) ; root -> right -> right -> right = newNode ( 2 ) ; cout << " Maximum ▁ Spiral ▁ Sum ▁ = ▁ " << maxSpiralSum ( root ) ; return 0 ; }