Posted on by Kalkicode
Code Binary Tree

Find top three elements of binary tree in php

Finding top 3 maximum node in binary tree

Php program for Find top three elements of binary tree. Here mentioned other language solution.

<?php
/* 
  Php program for
  Find top three elements in binary tree
*/
// Node of Binary Tree
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 $first;
	public $second;
	public $third;
	public	function __construct()
	{
		$this->root = NULL;
		$this->first = NULL;
		$this->second = NULL;
		$this->third = NULL;
	}
	// Recursive function
	// Display preorder view of binary tree
	public	function preOrder($node)
	{
		if ($node != NULL)
		{
			//Print node value
			echo "  ".strval($node->data);
			$this->preOrder($node->left);
			$this->preOrder($node->right);
		}
	}
	// Find top three largest nodes in binary tree
	public	function getTopThree($node)
	{
		if ($node != NULL)
		{
			if ($this->first == NULL)
			{
				// First node of tree
				$this->first = $node;
			}
			else if ($this->first->data < $node->data)
			{
				// When get new first largest node
				// Interchange the node values
				$this->third = $this->second;
				$this->second = $this->first;
				$this->first = $node;
			}
			else if ($this->second == NULL)
			{
				if ($this->first->data != $node->data)
				{
					// Get second largest node
					$this->second = $node;
				}
			}
			else
			{
				if ($this->second->data < $node->data && 
                    $this->first->data > $node->data)
				{
					// When we get new second largest
					// Replace the third node with the second node
					$this->third = $this->second;
					// This is new second largest element
					$this->second = $node;
				}
				else if ($this->third == NULL)
				{
					if ($this->second->data > $node->data && 
                        $this->first->data > $node->data)
					{
						// Get the third largest node
						$this->third = $node;
					}
				}
				else if ($this->third->data < $node->data && 
                         $this->first->data > $node->data && 
                         $this->second->data > $node->data)
				{
					$this->third = $node;
				}
			}
			// Recursively, execute left and right subtree
			$this->getTopThree($node->left);
			$this->getTopThree($node->right);
		}
	}
	// This are handle the request to finding
	// top three nodes in binary tree.
	public	function printTopThree()
	{
		if ($this->root == NULL)
		{
			return;
		}
		// Display tree elements
		echo "\n Preorder : ";
		$this->preOrder($this->root);
		// Set the initial all three nodes
		$this->first = NULL;
		$this->second = NULL;
		$this->third = NULL;
		// Find three largest element
		$this->getTopThree($this->root);
		// Display calculated result
		echo "\n First : ".($this->first->data), "\n";
		if ($this->second != NULL && 
            $this->second != $this->first && 
            $this->second->data < $this->first->data)
		{
			echo " Second : ".($this->second->data), "\n";
		}
		else
		{
			echo " Second : None \n";
		}
		if ($this->third != NULL && 
            $this->third != $this->second && 
            $this->third != $this->first && 
            $this->third->data < $this->second->data)
		{
			echo " Third : ".($this->third->data), "\n";
		}
		else
		{
			echo " Third : None\n";
		}
	}
	public static function main()
	{
		// Create two trees
		$x = new BinaryTree();
		$y = new BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		           10
		          /  \
		         /    \
		        6      8
		       / \    / \
		      12  3  7   5
		     /        \   \
		    9         -6  13
		*/
		// Add nodes
		$x->root = new TreeNode(10);
		$x->root->left = new TreeNode(6);
		$x->root->left->left = new TreeNode(12);
		$x->root->right = new TreeNode(8);
		$x->root->right->right = new TreeNode(5);
		$x->root->right->left = new TreeNode(7);
		$x->root->right->left->right = new TreeNode(-6);
		$x->root->left->right = new TreeNode(3);
		$x->root->left->left->left = new TreeNode(9);
		$x->root->right->right->right = new TreeNode(13);
		/*
		    Construct Tree
		    --------------
		         1
		        / \ 
		       /   \
		      1     2
		     /     / \
		    1     2   2
		*/
		// Add second tree node
		$y->root = new TreeNode(1);
		$y->root->left = new TreeNode(1);
		$y->root->right = new TreeNode(2);
		$y->root->right->right = new TreeNode(2);
		$y->root->right->left = new TreeNode(2);
		$y->root->left->left = new TreeNode(1);
		// Test One
		$x->printTopThree();
		// Test Two
		$y->printTopThree();
	}
}
BinaryTree::main();

Output

 Preorder :   10  6  12  9  3  8  7  -6  5  13
 First : 13
 Second : 12
 Third : 10

 Preorder :   1  1  1  2  2  2
 First : 2
 Second : 1
 Third : 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