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--;
}
}
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;
\$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)
{
\$s2->push(\$node->right);
}
if (\$node->left != NULL)
{
\$s2->push(\$node->left);
}
}
else
{
// Add node from left to right
// in s1 stack
if (\$node->left != NULL)
{
\$s1->push(\$node->left);
}
if (\$node->right != NULL)
{
\$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

*/
\$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.

Categories
Relative Post