Posted on by Kalkicode
Code Binary Tree

Reverse spiral traversal of a binary tree in php

Php program for Reverse spiral traversal of a binary tree. Here problem description and other solutions.

<?php
/*
  Php program for
  Reverse level order traversal in spiral form
*/
// 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;
	}
}
// Stack node
class StackNode
{
	// Stack data
	public $element;
	public $next;
	public	function __construct($element, $top)
	{
		$this->element = $element;
		$this->next = $top;
	}
}
// Define a custom stack
class MyStack
{
	public $top;
	public $size;
	public	function __construct()
	{
		$this->top = NULL;
		$this->size = 0;
	}
	// Add node at the top of stack
	public	function push($element)
	{
		$this->top = new StackNode($element, $this->top);
		$this->size++;
	}
	public	function isEmpty()
	{
		if ($this->size > 0 && $this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public	function pop()
	{
		if ($this->size > 0 && $this->top != NULL)
		{
			// Change top element of stack
			$this->top = $this->top->next;
			$this->size--;
		}
	}
	// Return top element of stack
	public	function peek()
	{
		if ($this->size == 0)
		{
			return NULL;
		}
		return $this->top->element;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Display tree element in reverse spiral level order traversal
	public	function reverseSpiral()
	{
		if ($this->root == NULL)
		{
			// Case
			// When empty
			echo "Empty Tree\n";
			return;
		}
		// Empty stack
		$s1 = new MyStack();
		$s2 = new MyStack();
		$result = new MyStack();
		// Some auxiliary variable
		$status = 1;
		$node = $this->root;
		// Add first node
		$s1->push($node);
		while ($node != NULL)
		{
			// Add node element into resultant stack
			$result->push($node);
			if ($status == 1)
			{
				// Add node from right to left
				// in s2 stack
				if ($node->right != NULL)
				{
					// Add right child
					$s2->push($node->right);
				}
				if ($node->left != NULL)
				{
					// Add left child
					$s2->push($node->left);
				}
			}
			else
			{
				// Add node from left to right
				// in s1 stack
				if ($node->left != NULL)
				{
					// Add left child
					$s1->push($node->left);
				}
				if ($node->right != NULL)
				{
					// Add right child
					$s1->push($node->right);
				}
			}
			if ($status == 1)
			{
				// Case A
				// When execute s1 stack
				// Remove s1 element
				$s1->pop();
				if ($s1->isEmpty())
				{
					// When after remove s1 element
					// s1 stack empty.
					// Then change stack by s2
					$status = 2;
					// Get first element of s2
					$node = $s2->peek();
				}
				else
				{
					// Otherwise get new top
					$node = $s1->peek();
				}
			}
			else
			{
				// Case B
				// When execute s2 stack
				// Remove s2 element
				$s2->pop();
				if ($s2->isEmpty())
				{
					// Here change stack
					$status = 1;
					$node = $s1->peek();
				}
				else
				{
					$node = $s2->peek();
				}
			}
		}
		// Display final result
		while ($result->isEmpty() == false)
		{
			// Get top element
			$node = $result->peek();
			// Display node value
			echo "   ".strval($node->data);
			// Remove top of stack
			$result->pop();
		}
	}
	public static function main()
	{
		// Create new tree
		$tree = new BinaryTree();
		/*   Make A Binary Tree
		    ---------------
		       1
		      / \ 
		     /   \
		    2     3
		   /     / \
		  4     5   6
		   \    \    \
		    7    8    9
		        
		*/
		// Add node
		$tree->root = new TreeNode(1);
		$tree->root->left = new TreeNode(2);
		$tree->root->right = new TreeNode(3);
		$tree->root->right->right = new TreeNode(6);
		$tree->root->right->left = new TreeNode(5);
		$tree->root->left->left = new TreeNode(4);
		$tree->root->left->left->right = new TreeNode(7);
		$tree->root->right->left->right = new TreeNode(8);
		$tree->root->right->right->right = new TreeNode(9);
		// Display reverse spiral level order element
		$tree->reverseSpiral();
	}
}
BinaryTree::main();

Output

   9   8   7   4   5   6   3   2   1

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