Skip to main content

Detect next node at same level of a key in binary tree in php

Next node of same level of tree

Php program for Detect next node at same level of a key in binary tree. Here mentioned other language solution.

<?php
/* 
  Php program for
  Find the next node of the key at the same 
  level in the 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;
	}
}
class BinaryTree
{
	public $root;
	public $status;
	public $result;
	public	function __construct()
	{
		$this->root = NULL;
		$this->status = -1;
		$this->result = NULL;
	}
	// Method which are find next node of same level
	public	function findNextNode($temp, $level, $node)
	{
		if ($temp != NULL)
		{
			if ($this->status == -1 && $temp->data == $node)
			{
				// When found node value
				$this->status = $level;
			}
			else if ($this->status == $level && 
                     $this->result == NULL)
			{
				// Next node of same level
				$this->result = $temp;
			}
			// Visit to left subtree
			$this->findNextNode($temp->left, $level + 1, $node);
			// Visit to right subtree
			$this->findNextNode($temp->right, $level + 1, $node);
		}
	}
	// This are handling the request of to finding next
	// node in same level by given node
	public	function nextNode($node)
	{
		// Reset the result indicator
		$this->status = -1;
		$this->result = NULL;
		// Find next node
		$this->findNextNode($this->root, 0, $node);
		echo "\n Node : $node\n";
		echo " Result : ";
		// Test Case
		if ($this->status == -1)
		{
			// Case A
			// When node values are not exist
			echo "Not found\n";
		}
		else if ($this->result == NULL)
		{
			// Case B
			// When next node is not found
			echo "None\n";
		}
		else
		{
			// Case C
			// When next node are exist
			printf("%d\n", $this->result->data);
		}
	}
	public static
	function main($args)
	{
		// Create new tree
		$tree = new BinaryTree();
		/*
		   Make A Binary Tree
		  ---------------------
		        1
		       / \ 
		      /   \ 
		     /     \
		    2       4
		   /       / \
		  /       /   \
		  3      6     5
		   \      \   /
		    7      8 11
		              
		*/
		// Add node in Binary Tree
		$tree->root = new TreeNode(1);
		$tree->root->left = new TreeNode(2);
		$tree->root->left->left = new TreeNode(3);
		$tree->root->left->left->right = new TreeNode(7);
		$tree->root->right = new TreeNode(4);
		$tree->root->right->right = new TreeNode(5);
		$tree->root->right->right->left = new TreeNode(11);
		$tree->root->right->left = new TreeNode(6);
		$tree->root->right->left->right = new TreeNode(8);
		// Testing
		$tree->nextNode(3);
		$tree->nextNode(7);
		$tree->nextNode(6);
		$tree->nextNode(5);
		$tree->nextNode(8);
		$tree->nextNode(1);
	}
}
BinaryTree::main(array());

Output

 Node : 3
 Result : 6

 Node : 7
 Result : 8

 Node : 6
 Result : 5

 Node : 5
 Result : None

 Node : 8
 Result : 11

 Node : 1
 Result : None




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