Maximum spiral sum in binary tree

Here given code implementation process.
// Java program for
// Maximum spiral sum in binary tree
import java.util.ArrayList;
import java.util.Stack;
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
// This are calculates the maximum spiral path
public int maxContiguous(ArrayList < Integer > path)
{
int n = path.size();
// Define some useful resultant auxiliary variables
// Get first element
int result = path.get(0);
int auxiliary = result;
// Executes the loop through by size of path
for (int i = 1; i < n; i++)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path.get(i);
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
}
return result;
}
// This is handle the request of finding maximum spiral path
public void maxSpiralSum()
{
if (this.root == null)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
ArrayList < Integer > path = new ArrayList < Integer > ();
// Define two auxiliary stack which is used to traverse spiral of binary tree.
Stack < TreeNode > s1 = new Stack < TreeNode > ();
Stack < TreeNode > s2 = new Stack < TreeNode > ();
// Add root to stack s1
s1.push(this.root);
// auxiliary temp variable
TreeNode temp = null;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!s1.isEmpty() || !s2.isEmpty())
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!s1.isEmpty())
{
// Get top node of s1 stack
temp = s1.peek();
// add node value
path.add(temp.data);
// Store the path from right to left
if (temp.right != null)
{
s2.push(temp.right);
}
if (temp.left != null)
{
s2.push(temp.left);
}
// Remove top element of s1 stack
s1.pop();
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!s2.isEmpty())
{
// Get top node of s2 stack
temp = s2.peek();
// add node value
path.add(temp.data);
// Store the path from left to right
if (temp.left != null)
{
s1.push(temp.left);
}
if (temp.right != null)
{
s1.push(temp.right);
}
// Remove top element of s2 stack
s2.pop();
}
}
// Display calculated result
System.out.println("Max spiral path sum : " + maxContiguous(path));
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = new TreeNode(-6);
tree.root.left = new TreeNode(4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(10);
tree.root.left.right.left.left = new TreeNode(1);
tree.root.left.right.right = new TreeNode(-4);
tree.root.left.right.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(-7);
tree.root.right.right = new TreeNode(-12);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(-9);
tree.maxSpiralSum();
}
}
input
Max spiral path sum : 16
// Include header file
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// C++ program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Define Binary Tree
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// This are calculates the maximum spiral path
int maxContiguous(vector < int > path)
{
int n = path.size();
// Define some useful resultant auxiliary variables
// Get first element
int result = path.at(0);
int auxiliary = result;
// Executes the loop through by size of path
for (int i = 1; i < n; i++)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path.at(i);
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
}
return result;
}
// This is handle the request of finding maximum spiral path
void maxSpiralSum()
{
if (this->root == NULL)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
vector < int > path ;
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
stack < TreeNode* > s1 ;
stack < TreeNode* > s2 ;
// Add root to stack s1
s1.push(this->root);
// auxiliary temp variable
TreeNode *temp = NULL;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!s1.empty() || !s2.empty())
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!s1.empty())
{
// Get top node of s1 stack
temp = s1.top();
// add node value
path.push_back(temp->data);
// Store the path from right to left
if (temp->right != NULL)
{
s2.push(temp->right);
}
if (temp->left != NULL)
{
s2.push(temp->left);
}
// Remove top element of s1 stack
s1.pop();
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!s2.empty())
{
// Get top node of s2 stack
temp = s2.top();
// add node value
path.push_back(temp->data);
// Store the path from left to right
if (temp->left != NULL)
{
s1.push(temp->left);
}
if (temp->right != NULL)
{
s1.push(temp->right);
}
// Remove top element of s2 stack
s2.pop();
}
}
// Display calculated result
cout << "Max spiral path sum : " << this->maxContiguous(path) << endl;
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree->root = new TreeNode(-6);
tree->root->left = new TreeNode(4);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(10);
tree->root->left->right->left->left = new TreeNode(1);
tree->root->left->right->right = new TreeNode(-4);
tree->root->left->right->right->right = new TreeNode(-1);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(-7);
tree->root->right->right = new TreeNode(-12);
tree->root->right->right->left = new TreeNode(5);
tree->root->right->right->right = new TreeNode(-9);
tree->maxSpiralSum();
return 0;
}
input
Max spiral path sum : 16
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Maximum spiral sum in binary tree
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
// This are calculates the maximum spiral path
public int maxContiguous(List < int > path)
{
int n = path.Count;
// Define some useful resultant auxiliary variables
// Get first element
int result = path[0];
int auxiliary = result;
// Executes the loop through by size of path
for (int i = 1; i < n; i++)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path[i];
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
}
return result;
}
// This is handle the request of finding maximum spiral path
public void maxSpiralSum()
{
if (this.root == null)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
List < int > path = new List < int > ();
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
Stack < TreeNode > s1 = new Stack < TreeNode > ();
Stack < TreeNode > s2 = new Stack < TreeNode > ();
// Add root to stack s1
s1.Push(this.root);
// auxiliary temp variable
TreeNode temp = null;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!(s1.Count == 0) || !(s2.Count == 0))
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!(s1.Count == 0))
{
// Get top node of s1 stack
temp = s1.Peek();
// add node value
path.Add(temp.data);
// Store the path from right to left
if (temp.right != null)
{
s2.Push(temp.right);
}
if (temp.left != null)
{
s2.Push(temp.left);
}
// Remove top element of s1 stack
s1.Pop();
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!(s2.Count == 0))
{
// Get top node of s2 stack
temp = s2.Peek();
// add node value
path.Add(temp.data);
// Store the path from left to right
if (temp.left != null)
{
s1.Push(temp.left);
}
if (temp.right != null)
{
s1.Push(temp.right);
}
// Remove top element of s2 stack
s2.Pop();
}
}
// Display calculated result
Console.WriteLine("Max spiral path sum : " + this.maxContiguous(path));
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = new TreeNode(-6);
tree.root.left = new TreeNode(4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(10);
tree.root.left.right.left.left = new TreeNode(1);
tree.root.left.right.right = new TreeNode(-4);
tree.root.left.right.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(-7);
tree.root.right.right = new TreeNode(-12);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(-9);
tree.maxSpiralSum();
}
}
input
Max spiral path sum : 16
<?php
// Php program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
// This are calculates the maximum spiral path
public function maxContiguous($path)
{
$n = count($path);
// Define some useful resultant auxiliary variables
// Get first element
$result = $path[0];
$auxiliary = $result;
// Executes the loop through by size of path
for ($i = 1; $i < $n; $i++)
{
// Add new element into auxiliary variable
$auxiliary = $auxiliary + $path[$i];
if ($result < $auxiliary)
{
// When auxiliary contain new result
$result = $auxiliary;
}
if ($auxiliary < 0)
{
// When auxiliary are less than zero
$auxiliary = 0;
}
}
return $result;
}
// This is handle the request of finding maximum spiral path
public function maxSpiralSum()
{
if ($this->root == NULL)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
$path = array();
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
$s1 = array();
$s2 = array();
// Add root to stack s1
array_unshift($s1, $this->root);
// auxiliary temp variable
$temp = NULL;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!empty($s1) || !empty($s2))
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!empty($s1))
{
// Get top node of s1 stack
$temp = $s1[0];
// add node value
$path[] = $temp->data;
// Store the path from right to left
if ($temp->right != NULL)
{
array_unshift($s2, $temp->right);
}
if ($temp->left != NULL)
{
array_unshift($s2, $temp->left);
}
// Remove top element of s1 stack
array_shift($s1);
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!empty($s2))
{
// Get top node of s2 stack
$temp = $s2[0];
// add node value
$path[] = $temp->data;
// Store the path from left to right
if ($temp->left != NULL)
{
array_unshift($s1, $temp->left);
}
if ($temp->right != NULL)
{
array_unshift($s1, $temp->right);
}
// Remove top element of s2 stack
array_shift($s2);
}
}
// Display calculated result
echo("Max spiral path sum : ".$this->maxContiguous($path).
"\n");
}
}
function main()
{
$tree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
$tree->root = new TreeNode(-6);
$tree->root->left = new TreeNode(4);
$tree->root->left->right = new TreeNode(3);
$tree->root->left->right->left = new TreeNode(10);
$tree->root->left->right->left->left = new TreeNode(1);
$tree->root->left->right->right = new TreeNode(-4);
$tree->root->left->right->right->right = new TreeNode(-1);
$tree->root->left->left = new TreeNode(2);
$tree->root->right = new TreeNode(-7);
$tree->root->right->right = new TreeNode(-12);
$tree->root->right->right->left = new TreeNode(5);
$tree->root->right->right->right = new TreeNode(-9);
$tree->maxSpiralSum();
}
main();
input
Max spiral path sum : 16
// Node JS program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
this.root = null;
}
// This are calculates the maximum spiral path
maxContiguous(path)
{
var n = path.length;
// Define some useful resultant auxiliary variables
// Get first element
var result = path[0];
var auxiliary = result;
// Executes the loop through by size of path
for (var i = 1; i < n; i++)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path[i];
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
}
return result;
}
// This is handle the request of finding maximum spiral path
maxSpiralSum()
{
if (this.root == null)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
var path = [];
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
var s1 = [];
var s2 = [];
// Add root to stack s1
s1.push(this.root);
// auxiliary temp variable
var temp = null;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!(s1.length == 0) || !(s2.length == 0))
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!(s1.length == 0))
{
// Get top node of s1 stack
temp = s1[s1.length - 1];
// add node value
path.push(temp.data);
// Store the path from right to left
if (temp.right != null)
{
s2.push(temp.right);
}
if (temp.left != null)
{
s2.push(temp.left);
}
// Remove top element of s1 stack
s1.pop();
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!(s2.length == 0))
{
// Get top node of s2 stack
temp = s2[s2.length - 1];
// add node value
path.push(temp.data);
// Store the path from left to right
if (temp.left != null)
{
s1.push(temp.left);
}
if (temp.right != null)
{
s1.push(temp.right);
}
// Remove top element of s2 stack
s2.pop();
}
}
// Display calculated result
console.log("Max spiral path sum : " + this.maxContiguous(path));
}
}
function main()
{
var tree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = new TreeNode(-6);
tree.root.left = new TreeNode(4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(10);
tree.root.left.right.left.left = new TreeNode(1);
tree.root.left.right.right = new TreeNode(-4);
tree.root.left.right.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(-7);
tree.root.right.right = new TreeNode(-12);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(-9);
tree.maxSpiralSum();
}
main();
input
Max spiral path sum : 16
# Python 3 program for
# Maximum spiral sum in binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
self.root = None
# This are calculates the maximum spiral path
def maxContiguous(self, path) :
n = len(path)
result = path[0]
auxiliary = result
# Executes the loop through by size of path
i = 1
while (i < n) :
# Add new element into auxiliary variable
auxiliary = auxiliary + path[i]
if (result < auxiliary) :
# When auxiliary contain new result
result = auxiliary
if (auxiliary < 0) :
# When auxiliary are less than zero
auxiliary = 0
i += 1
return result
# This is handle the request of finding maximum spiral path
def maxSpiralSum(self) :
if (self.root == None) :
# When tree is empty
return
path = []
s1 = []
s2 = []
# Add root to stack s1
s1.insert(0,self.root)
temp = None
# This loop execute until auxiliary stack s1 and s2 are not empty
while (len(s1) > 0 or len(s2) > 0) :
# Execute loop until s1 stack are not empty
# And store the current level node in s2 stack
while (len(s1) > 0) :
# Get top node of s1 stack
temp = s1[0]
# add node value
path.append(temp.data)
# Store the path from right to left
if (temp.right != None) :
s2.insert(0,temp.right)
if (temp.left != None) :
s2.insert(0,temp.left)
# Remove top element of s1 stack
s1.pop(0)
# Execute loop until s2 stack are not empty
# And store the current level node in s1 stack
while (len(s2) > 0) :
# Get top node of s2 stack
temp = s2[0]
# Add node value
path.append(temp.data)
# Store the path from left to right
if (temp.left != None) :
s1.insert(0,temp.left)
if (temp.right != None) :
s1.insert(0,temp.right)
# Remove top element of s2 stack
s2.pop(0)
# Display calculated result
print("Max spiral path sum : ", self.maxContiguous(path))
def main() :
tree = BinaryTree()
# Create Binary Tree
# -----------------
# -6
# / \
# 4 -7
# / \ \
# 2 3 -12
# / \ / \
# 10 -4 5 -9
# / \
# 1 -1
tree.root = TreeNode(-6)
tree.root.left = TreeNode(4)
tree.root.left.right = TreeNode(3)
tree.root.left.right.left = TreeNode(10)
tree.root.left.right.left.left = TreeNode(1)
tree.root.left.right.right = TreeNode(-4)
tree.root.left.right.right.right = TreeNode(-1)
tree.root.left.left = TreeNode(2)
tree.root.right = TreeNode(-7)
tree.root.right.right = TreeNode(-12)
tree.root.right.right.left = TreeNode(5)
tree.root.right.right.right = TreeNode(-9)
tree.maxSpiralSum()
if __name__ == "__main__": main()
input
Max spiral path sum : 16
# Ruby program for
# Maximum spiral sum in binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# This are calculates the maximum spiral path
def maxContiguous(path)
n = path.length
# Define some useful resultant auxiliary variables
# Get first element
result = path[0]
auxiliary = result
# Executes the loop through by size of path
i = 1
while (i < n)
# Add new element into auxiliary variable
auxiliary = auxiliary + path[i]
if (result < auxiliary)
# When auxiliary contain new result
result = auxiliary
end
if (auxiliary < 0)
# When auxiliary are less than zero
auxiliary = 0
end
i += 1
end
return result
end
# This is handle the request of finding maximum spiral path
def maxSpiralSum()
if (self.root == nil)
# When tree is empty
return
end
# It will be use assemble a spiral traverse path.
path = []
# Define two auxiliary stack which is used to
# traverse spiral of binary tree.
s1 = []
s2 = []
# Add root to stack s1
s1.push(self.root)
# auxiliary temp variable
temp = nil
# This loop execute until auxiliary stack s1 and s2 are not empty
while (!(s1.length == 0) || !(s2.length == 0))
# Execute loop until s1 stack are not empty
# And store the current level node in s2 stack
while (!(s1.length == 0))
# Get top node of s1 stack
temp = s1.last
# add node value
path.push(temp.data)
# Store the path from right to left
if (temp.right != nil)
s2.push(temp.right)
end
if (temp.left != nil)
s2.push(temp.left)
end
# Remove top element of s1 stack
s1.pop()
end
# Execute loop until s2 stack are not empty
# And store the current level node in s1 stack
while (!(s2.length == 0))
# Get top node of s2 stack
temp = s2.last
# add node value
path.push(temp.data)
# Store the path from left to right
if (temp.left != nil)
s1.push(temp.left)
end
if (temp.right != nil)
s1.push(temp.right)
end
# Remove top element of s2 stack
s2.pop()
end
end
# Display calculated result
print("Max spiral path sum : ", self.maxContiguous(path), "\n")
end
end
def main()
tree = BinaryTree.new()
# Create Binary Tree
# -----------------
# -6
# / \
# 4 -7
# / \ \
# 2 3 -12
# / \ / \
# 10 -4 5 -9
# / \
# 1 -1
tree.root = TreeNode.new(-6)
tree.root.left = TreeNode.new(4)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.left = TreeNode.new(10)
tree.root.left.right.left.left = TreeNode.new(1)
tree.root.left.right.right = TreeNode.new(-4)
tree.root.left.right.right.right = TreeNode.new(-1)
tree.root.left.left = TreeNode.new(2)
tree.root.right = TreeNode.new(-7)
tree.root.right.right = TreeNode.new(-12)
tree.root.right.right.left = TreeNode.new(5)
tree.root.right.right.right = TreeNode.new(-9)
tree.maxSpiralSum()
end
main()
input
Max spiral path sum : 16
import scala.collection.mutable._;
// Scala program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// This are calculates the maximum spiral path
def maxContiguous(path: ArrayBuffer[Int]): Int = {
var n: Int = path.size;
// Define some useful resultant auxiliary variables
// Get first element
var result: Int = path(0);
var auxiliary: Int = result;
// Executes the loop through by size of path
var i: Int = 1;
while (i < n)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path(i);
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
i += 1;
}
return result;
}
// This is handle the request of finding maximum spiral path
def maxSpiralSum(): Unit = {
if (this.root == null)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
var s1 = Stack[TreeNode]();
var s2 = Stack[TreeNode]();;
// Add root to stack s1
s1.push(this.root);
// auxiliary temp variable
var temp: TreeNode = null;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!s1.isEmpty || !s2.isEmpty)
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!s1.isEmpty)
{
// Get top node of s1 stack
temp = s1.top;
// add node value
path += temp.data;
// Store the path from right to left
if (temp.right != null)
{
s2.push(temp.right);
}
if (temp.left != null)
{
s2.push(temp.left);
}
// Remove top element of s1 stack
s1.pop;
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!s2.isEmpty)
{
// Get top node of s2 stack
temp = s2.top;
// add node value
path += temp.data;
// Store the path from left to right
if (temp.left != null)
{
s1.push(temp.left);
}
if (temp.right != null)
{
s1.push(temp.right);
}
// Remove top element of s2 stack
s2.pop;
}
}
// Display calculated result
println("Max spiral path sum : " + maxContiguous(path));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = new TreeNode(-6);
tree.root.left = new TreeNode(4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(10);
tree.root.left.right.left.left = new TreeNode(1);
tree.root.left.right.right = new TreeNode(-4);
tree.root.left.right.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(-7);
tree.root.right.right = new TreeNode(-12);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.right = new TreeNode(-9);
tree.maxSpiralSum();
}
}
input
Max spiral path sum : 16
import Foundation
// Swift 4 program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// implement stack
struct Stack
{
private
var items: [TreeNode?] = []
func peek()->TreeNode?
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()->TreeNode?
{
return items.removeFirst()
}
mutating func push(_ data: TreeNode?)
{
items.insert(data, at: 0)
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// This are calculates the maximum spiral path
func maxContiguous(_ path: [Int] )->Int
{
let n: Int = path.count;
// Define some useful resultant auxiliary variables
// Get first element
var result: Int = path[0];
var auxiliary: Int = result;
// Executes the loop through by size of path
var i: Int = 1;
while (i < n)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path[i];
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
i += 1;
}
return result;
}
// This is handle the request of finding maximum spiral path
func maxSpiralSum()
{
if (self.root == nil)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
var path = [Int]();
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
var s1: Stack = Stack();
var s2: Stack = Stack();
// Add root to stack s1
s1.push(self.root);
// auxiliary temp variable
var temp: TreeNode? = nil;
// This loop execute until auxiliary stack s1 and s2 are not empty
while (!s1.isEmpty() || !s2.isEmpty())
{
// Execute loop until s1 stack are not empty
// And store the current level node in s2 stack
while (!s1.isEmpty())
{
// Get top node of s1 stack
temp = s1.pop();
// add node value
path.append(temp!.data);
// Store the path from right to left
if (temp!.right != nil)
{
s2.push(temp!.right);
}
if (temp!.left != nil)
{
s2.push(temp!.left);
}
}
// Execute loop until s2 stack are not empty
// And store the current level node in s1 stack
while (!s2.isEmpty())
{
// Get top node of s2 stack
temp = s2.pop();
// add node value
path.append(temp!.data);
// Store the path from left to right
if (temp!.left != nil)
{
s1.push(temp!.left);
}
if (temp!.right != nil)
{
s1.push(temp!.right);
}
}
}
// Display calculated result
print("Max spiral path sum : ", self.maxContiguous(path));
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = TreeNode(-6);
tree.root!.left = TreeNode(4);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.left = TreeNode(10);
tree.root!.left!.right!.left!.left = TreeNode(1);
tree.root!.left!.right!.right = TreeNode(-4);
tree.root!.left!.right!.right!.right = TreeNode(-1);
tree.root!.left!.left = TreeNode(2);
tree.root!.right = TreeNode(-7);
tree.root!.right!.right = TreeNode(-12);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.right!.right!.right = TreeNode(-9);
tree.maxSpiralSum();
}
main();
input
Max spiral path sum : 16
import java.util.Stack;
// Kotlin program for
// Maximum spiral sum in binary tree
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// This are calculates the maximum spiral path
fun maxContiguous(path: MutableList<Int> ): Int
{
val n: Int = path.size;
// Define some useful resultant auxiliary variables
// Get first element
var result: Int = path[0];
var auxiliary: Int = result;
var i: Int = 1;
while (i < n)
{
// Add new element into auxiliary variable
auxiliary = auxiliary + path[i];
if (result < auxiliary)
{
// When auxiliary contain new result
result = auxiliary;
}
if (auxiliary < 0)
{
// When auxiliary are less than zero
auxiliary = 0;
}
i += 1;
}
return result;
}
// This is handle the request of finding maximum spiral path
fun maxSpiralSum(): Unit
{
if (this.root == null)
{
// When tree is empty
return;
}
// It will be use assemble a spiral traverse path.
val path = mutableListOf<Int>();
// Define two auxiliary stack which is used to
// traverse spiral of binary tree.
val s1 = Stack<TreeNode?>();
val s2 = Stack<TreeNode?>();
// Add root to stack s1
s1.push(this.root);
// auxiliary temp variable
var temp: TreeNode? ;
while (!s1.empty() || !s2.empty())
{
while (!s1.empty())
{
// Get top node of s1 stack
temp = s1.peek();
// add node value
path.add(temp!!.data);
// Store the path from right to left
if (temp.right != null)
{
s2.push(temp.right);
}
if (temp.left != null)
{
s2.push(temp.left);
}
// Remove top element of s1 stack
s1.pop();
}
while (!s2.empty())
{
// Get top node of s2 stack
temp = s2.peek();
// Add node value
path.add(temp!!.data);
// Store the path from left to right
if (temp.left != null)
{
s1.push(temp.left);
}
if (temp.right != null)
{
s1.push(temp.right);
}
// Remove top element of s2 stack
s2.pop();
}
}
// Display calculated result
println("Max spiral path sum : " + this.maxContiguous(path));
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Create Binary Tree
-----------------
-6
/ \
4 -7
/ \ \
2 3 -12
/ \ / \
10 -4 5 -9
/ \
1 -1
*/
tree.root = TreeNode(-6);
tree.root?.left = TreeNode(4);
tree.root?.left?.right = TreeNode(3);
tree.root?.left?.right?.left = TreeNode(10);
tree.root?.left?.right?.left?.left = TreeNode(1);
tree.root?.left?.right?.right = TreeNode(-4);
tree.root?.left?.right?.right?.right = TreeNode(-1);
tree.root?.left?.left = TreeNode(2);
tree.root?.right = TreeNode(-7);
tree.root?.right?.right = TreeNode(-12);
tree.root?.right?.right?.left = TreeNode(5);
tree.root?.right?.right?.right = TreeNode(-9);
tree.maxSpiralSum();
}
input
Max spiral path sum : 16
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment