Skip to main content

PHP code to find the diameter of tree in O(n) time complexity

<?php


class BinaryNode{
        public $value = null; // node value 
        public $left = null; // left child 
        public $right = null; // right child 
        
        public function __construct($value) {
                $this->value = $value;
        }        
}

class BinaryTreeDiameter{        
        //find the diameter and print its value
        public function findDiameterOfTree($root){
        //Checking node is empty or not                
                if($root === null){
                        return 0;
                }
                
                //  Compute the depth of each subtree
                $lDepth = $this->findDiameterOfTree($root->left); 
                $rDepth = $this->findDiameterOfTree($root->right); 

                // Return the greater one.
                 if ($lDepth > $rDepth) 
            return $lDepth+1;
        else 
            return $rDepth+1;
        }
        
        //find the diameter and print its value
}

$Dia = new BinaryTreeDiameter(1);   
$Dia->root = new BinaryNode(1);  
$Dia->root->left = new BinaryNode(2);  
$Dia->root->right = new BinaryNode(3);  
$Dia->root->left->left = new BinaryNode(4);  
$Dia->root->left->right = new BinaryNode(5);  
$Dia->root->right->left = new BinaryNode(6);  
$Dia->root->right->right = new BinaryNode(7);  
$Dia->root->left->left->left = new BinaryNode(8);  
            
//Display the maximum width of given tree  
print "Maximum width of the binary tree: " . $Dia->findDiameterOfTree($Dia->root); 
?>

Comments

Popular posts from this blog

PHP function for checking IMEI

Luhn algorithm for IMEI Check public function __checkIMEI($imei){ if(strlen($imei)==15){ $imeia=($imei[1]*2); if(strlen($imeia)==2){$imeia=str_split($imeia,1); $imeia=$imeia[0]+$imeia[1]; } $imeib=($imei[3]*2); if(strlen($imeib)==2){$imeib=str_split($imeib,1); $imeib=$imeib[0]+$imeib[1]; } $imeic=($imei[5]*2); if(strlen($imeic)==2){$imeic=str_split($imeic,1); $imeic=$imeic[0]+$imeic[1]; } $imeid=($imei[7]*2); if(strlen($imeid)==2){$imeid=str_split($imeid,1); $imeid=$imeid[0]+$imeid[1];} $imeie=($imei[9]*2); if(strlen($imeie)==2){$imeie=str_split($imeie,1); $imeie=$imeie[0]+$imeie[1]; } $imeif=($imei[11]*2); if(strlen($imeif)==2){$imeif=str_split($imeif,1); $imeif=$imeif[0]+$imeif[1]; } $imeig=($imei[13]*2); if(strlen($imeig)==2){$imeig=str_split($imeig,1); $imeig=$imeig[0]+$imeig[1]; } $IMEI= ($ime...

PHP code for Implementing LRU cache.

<?php interface LRUCache{ /** •@param string $key •@param string $value •@return bool $result • •Stores value against the key in the cache */ public function insertIntoCache($key,$value); /** •@param string $key •@return string $value •Gets the value of a key from the cache */ public function getFromCache($key); /** Purge the entire cache */ public function purgeCache(); /** •@return int $count •Gets the number of successful cache hits so far */ public function allCacheHits(); /** •@return int $count •Gets the number of unsuccessful cache hits so far **/ public function allCacheMissed(); } class Cache implements LRUCache{ // int the max number of elements the cache supports private $capaci...

Magic Function in PHP (__sleep() and __wakeup() )

There are many magic methods in PHP like  __construct(), __destruct(), __callback(), __get(), __set(), __sleep(), __wake() and many more. But we will be takingon  on  __sleep() and  __wake(). __sleep() : serialize() checks if your class has a function with the magic name __sleep(). If so, that function is executed prior to any serialization. It can clean up the object and is supposed to return an array with the names of all variables of that object that should be serialized. If the method doesn't return anything then NULL is serialized and E_NOTICE is issued. serialize() is used for the representation of the storage class for storing the value. Serializing   an object means converting it to a byte stream representation that can be stored in a file. The use of __sleep()  to commit the pending task. If a bulk data is being inserted then at that time __sleep can be used. it will not release the object unless the work is not completed....