Maximum spiral sum in Binary Tree

Introduction

In this blog, we will be discussing the problem of the Maximum spiral sum in Binary Tree.

A binary tree is a data structure in which each parent node has no more than two children. A binary tree node is made up of three components:

• data
• pointer to left
• pointer to right

Spiral order traversal

In spiral traversal, Level 1 nodes should be printed first from left to right, then level 2 nodes from right to left, then level 3 nodes from left to right, and so on. In other words, odd levels should be printed from left to right and even levels from right to left, or vice versa.
 

The spiral level order traversal for the following tree is-

(1, 3, 2, 4, 5, 6, 7) or (1, 2, 3, 7, 6, 5, 4)

Let us understand the problem statement of the Maximum spiral sum in Binary Tree.

Problem Statement

We will have a binary tree containing n nodes in the problem “Maximum spiral sum in Binary Tree.” We must find the maximum sum obtained when the tree is traversed spirally. In the spiral traversal of a tree, one by one, all levels are traversed where the root level is traversed from right to left, the next level from left to right, and so on.

Before we deep dive into the solution to this problem, we should look at an example to understand the problem of Maximum spiral sum in Binary Tree better. 

Example

Input:
 

Output: 

The maximum spiral sum is: 6

Explanation:

The spiral level order traversal for the following tree is

(1, -1, 5, -4, 6, -9, 1) or (1, 5, -1, 1, -9, 6, -4)

We are getting (1+5) = 6 as the maximum sum.

Approach

We will use two stacks to obtain the level order traversal in the spiral form of the given binary tree and store it in an array. Find the maximum sum sub-array of the resulting spiralTraversal array.

Algorithm

• Initialize an array that will store the spiral traversal of the tree.
• We will traverse half of the rows from the left to the right direction and half of the rows in right to left direction.
• Use two stacks to find spiral traversal. One stack will store the traversal of rows that are traversed from left to right, and the other will store the traversal of rows that are stored from right to left
• Use Kadane’s algorithm to find the maximum sum sub-array.

Implementation in C++

// function to find maximum spiral sum in binary tree
#include <bits/stdc++.h>

using namespace std;

// structure of a node of binary tree
struct Node
{
   int data;
   Node *left, *right;
};

// creating a new node
Node *newNode(int data)
{
   Node *node = new Node;

   node->data = data;
   node->left = node->right = NULL;

   return node;
}

int main()
{
   // creating tree
   Node *root = newNode(-4);
   root->left = newNode(-9);
   root->right = newNode(-1);
   root->left->left = newNode(5);
   root->left->right = newNode(1);
   root->right->left = newNode(-2);
   root->right->right = newNode(4);
   root->left->left->left = newNode(-6);
   root->right->right->right = newNode(2);

   // storing spiral traversal   

   // Create two stacks to store alternate levels

   // For levels from right to left
   stack<Node *> traversalRightToLeft;

   // For levels from left to right
   stack<Node *> traversalLeftToRight;

   vector<int> spiralTraversal;

   // Push first level to first stack 'traversalRightToLeft'
   traversalRightToLeft.push(root);

   while (!traversalRightToLeft.empty() || !traversalLeftToRight.empty())
   {

      // traverse current level from traversalRightToLeft and
      // push nodes of next level to traversalLeftToRight
      while (!traversalRightToLeft.empty())
      {
         Node *temp = traversalRightToLeft.top();
         traversalRightToLeft.pop();

         // push temp-data to 'spiralTraversal'
         spiralTraversal.push_back(temp->data);

         // Note that right is pushed before left
         if (temp->right)
            traversalLeftToRight.push(temp->right);
         if (temp->left)
            traversalLeftToRight.push(temp->left);
      }

      // traverse current level from traversalLeftToRight and
      // push nodes of next level to traversalRightToLeft
      while (!traversalLeftToRight.empty())
      {
         Node *temp = traversalLeftToRight.top();
         traversalLeftToRight.pop();

         // push temp-data to 'spiralTraversal'
         spiralTraversal.push_back(temp->data);

         // Note that left is pushed before right
         if (temp->left)
            traversalRightToLeft.push(temp->left);
         if (temp->right)
            traversalRightToLeft.push(temp->right);
      }
   }

   // using kadane’s algorithm to find the maximum subspiralTraversalay sum
   int maxTillHere = INT_MIN, maxSum = INT_MIN, n = spiralTraversal.size();

   for (int i = 0; i < n; i++)
   {
      if (maxTillHere < 0)
         maxTillHere = spiralTraversal[i];

      else
         maxTillHere += spiralTraversal[i];

      maxSum = max(maxSum, maxTillHere);
   }
   cout << maxSum << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Output: 

8

Algorithm Complexity

Time Complexity: O(N)

We traverse the tree once, which takes O(n) time. Finding the maximum sum sub-array using kadane’s algorithm takes O(n) time. Hence time complexity is O(n) + O(n) ~ O(n).

Space Complexity: O(N)

We are storing the nodes in the spiralTraversal array. Thus space complexity of this solution is linear.