Skip to main content

Maximum spiral sum in binary tree

Maximum spiral sum in a 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
Last updated on by Kalkicode




Comment

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