Skip to main content

Inorder traversal of binary tree using stack in php

Php program for Inorder traversal of binary tree using stack. Here problem description and explanation.

<?php
// Php program for
// Inorder traversal without recursion
// Using stack

// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	// Make a tree node
	public	function __construct($data)
	{
		// Set node data
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
// Stack Class
class MyStack
{
	public $top;
	public $size;
	public	function __construct()
	{
		$this->top = NULL;
		$this->size = 0;
	}
	// Add new element into stack
	public	function push($element)
	{
		// Create new node
		$node = new StackNode($element);
		$node->next = $this->top;
		// new node is new top
		$this->top = $node;
		// Increase the size
		$this->size += 1;
	}
	// Remove top element of the stack
	public	function pop()
	{
		if ($this->top != NULL)
		{
			// next node is new top
			$this->top = $this->top->next;
			// Reduce size
			$this->size -= 1;
		}
	}
	// Returns the status of empty or non empty stacks
	public	function isEmpty()
	{
		if ($this->size > 0 && $this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Return top element of stack
	public	function peek()
	{
		if ($this->isEmpty())
		{
			return NULL;
		}
		return $this->top->element;
	}
}
class StackNode
{
	public $element;
	public $next;
	public	function __construct($element)
	{
		$this->element = $element;
		$this->next = NULL;
	}
}

class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Display Inorder view of binary tree
	public	function inorder()
	{
		if ($this->root != NULL)
		{
			// Make new stack
			$s = new MyStack();
			$node = $this->root;
			// Display tree element
			while (!$s->isEmpty() || $node != NULL)
			{
				if ($node != NULL)
				{
					// Add current node
					$s->push($node);
					// Visit to left subtree
					$node = $node->left;
				}
				else
				{
					// When node is null
					// Get stack top element
					$node = $s->peek();
					// Display node value
					printf("%s", " ".strval($node->data));
					// Remove top element of the stack
					$s->pop();
					// Visit to left subtree of current node
					$node = $node->right;
				}
			}
		}
		else
		{
			printf("%s", "Empty Linked List\n");
		}
	}
	public static
	function main($args)
	{
		// Create new tree
		$tree = new BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		        15
		       /  \
		      24   54
		     /    /  \
		    35   62   13
		*/
		// Add tree nodes
		$tree->root = new TreeNode(15);
		$tree->root->left = new TreeNode(24);
		$tree->root->right = new TreeNode(54);
		$tree->root->right->right = new TreeNode(13);
		$tree->root->right->left = new TreeNode(62);
		$tree->root->left->left = new TreeNode(35);
		// Display result
		$tree->inorder();
	}
}
BinaryTree::main(array());

Output

 35 24 15 62 54 13




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