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...

PHP code for finding Longest Repeated Substrings (LRS)

<?php Class LRS{ /** •@param array $texts •Prints longest repeated substrings for each text */ public static function getAllLRS($texts){ $stringArr = array(); foreach($texts as $string){ $stringArr[] = self::LongestRepeatedSubstring($string); } return $stringArr; } public function LongestRepeatedSubstring($string){ if ($string == null) return null; $string_length = strlen($string); $substrings = array(); for ($i=0; $i < $string_length; $i++){ $substrings[$i] = substr($string, $i); } sort($substrings); $result = ""; for ($i = 0; $i < $string_length - 1; $i++){ $lcs = self::LongestCommonString($substrings[$i], $substrings[$i ...