Insertion in binary search tree without recursion in php

Php program for Insertion in binary search tree without recursion. Here problem description and other solutions.

<?php
// Php program for
// iterative insert in binary search tree
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// insert a element
	public	function addNode($data)
	{
		// Create a new node
		$node = new TreeNode($data);
		if ($this->root == NULL)
		{
			// When adds a first node in bst
			$this->root = $node;
		}
		else
		{
			$find = $this->root;
			// Add new node to proper position
			while ($find != NULL)
			{
				if ($find->data >= $data)
				{
					if ($find->left == NULL)
					{
						// When left child empty
						// So add new node here
						$find->left = $node;
						return;
					}
					else
					{
						// Otherwise
						// Visit left sub-tree
						$find = $find->left;
					}
				}
				else
				{
					if ($find->right == NULL)
					{
						// When right child empty
						// So add new node here
						$find->right = $node;
						return;
					}
					else
					{
						// Visit right sub-tree
						$find = $find->right;
					}
				}
			}
		}
	}
	// Display preorder
	public	function preorder($node)
	{
		if ($node != NULL)
		{
			// Display node value
			echo "  $node->data";
			// Visit to left subtree
			$this->preorder($node->left);
			// Visit to right subtree
			$this->preorder($node->right);
		}
	}
	public	function inorder($node)
	{
		if ($node != NULL)
		{
			// Visit to left subtree
			$this->inorder($node->left);
			// Display node value
			echo "  $node->data";
			// Visit to right subtree
			$this->inorder($node->right);
		}
	}
	public	function postorder($node)
	{
		if ($node != NULL)
		{
			// Visit to left subtree
			$this->postorder($node->left);
			// Visit to right subtree
			$this->postorder($node->right);
			// Display node value
			echo "  $node->data";
		}
	}
	public static
	function main($args)
	{
		$tree = new BinarySearchTree();
		/*
		         10
		        / \
		       /   \
		      4     15
		     / \   /
		    3   5 12
		    -------------
		    Build binary search tree

		*/
		$tree->addNode(10);
		$tree->addNode(4);
		$tree->addNode(3);
		$tree->addNode(5);
		$tree->addNode(15);
		$tree->addNode(12);
		// Display tree nodes
		echo "Preorder \n";
		$tree->preorder($tree->root);
		echo "\nInorder \n";
		$tree->inorder($tree->root);
		echo "\nPostorder \n";
		$tree->postorder($tree->root);
	}
}
BinarySearchTree::main(array());

Output

Preorder
  10  4  3  5  15  12
Inorder
  3  4  5  10  12  15
Postorder
  3  5  4  12  15  10


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







© 2021, kalkicode.com, All rights reserved