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 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 $capacity; // Array representing a naive hashmap (TODO needs to pass t

PHP code for finding distinct elements common to all rows of a matrix in O(n) time complexity

<?php class Matrix{ /** •@param 2D array $matrix • •Prints distinct elements common to all rows of the matrix */ public static function getDistinctElementsCommonToAllRows($matrix){ // A hash map to store count of elements $hashmap = array(); $selectedHash = array(); $rows = count($matrix); $cols = count($matrix[0]); for ($i = 0; $i < $rows; $i++) { // Increment the count of first // element of the row if(array_key_exists($matrix[$i][0],$hashmap)){ $hashmap[$matrix[$i][0]] = $i+1; } // Starting from the second element // of the current row for ($j = 1; $j < $cols; $j++) { // If current ele

Code for Mail in PHP

PHP mail function and mail configuration in  XAMPP  and sending mail is done from sendmail through localhost. I hope it will help you. mail() function <? php $to = 'dubeynitish22@hotmail.com' ; $subject = 'Test' ; $message = 'Hello' ; $headers = 'From: webmaster@example.com' . "\r\n" . 'Reply-To: webmaster@example.com' . "\r\n" . 'X-Mailer: PHP/' . phpversion ();   if (! mail ( $to , $subject , $message , $headers )){ echo "Error !!" ; } else { echo "Email Sent !!" ; } ?> 2. php.ini configuration (For SEND-MAIL) [ mail function ] ; For Win32 only . ; http : //php.net/smtp ; SMTP = localhost ; http : //php.net/smtp-port ; smtp_port = 25   ; For Win32 only . ; http : //php.net/sendmail-from ; sendmail_from = me@example . com   ; For Unix only . You may supply arguments as well ( default : "sendmail -t -i&q