Skip to main content

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

Image
By 
<?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); 
?>
Labels:

Comments

Post a Comment

Popular posts from this blog

PHP code for finding Longest Repeated Substrings (LRS)

By
<?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 ...
Post a Comment
Read more

Write a function that checks if a given word stored in a doubly linked list is a palindrome.

By
<?php class Node { public $value; public $next = null; // next node public $prev = null; // previous node public function __construct($value) { $this->value = $value; } } class Palindrome { /** •@param string $word •@return bool */ public static function isPalindrome($head, $tail){ if ($head == null) return true; while ($head != $tail){ if ($head->value != $tail->value) return false; $head = $head->next; $tail = $tail->prev; } return true; } } $head = new Node(1); $firstNode = new Node(2); $secondNode = new Node(3); $tail = new Node(4); $head->next = $firstNode; $firstNode->prev = $head; $firstNode->next = $secondNode;...
Post a Comment
Read more

What Make Facebook page load faster ?

By
Facebook has a “ Lazy Loading ” system they call “ BigPipe ” that helps the pages load fast. Facebook breaks each page down into sections they call “ Pagelets” , and using Javascript only load the most important Pagelets first then load the less important ones shortly afterward. And pipeline them through several execution stages inside web servers and browsers, as the modern microprocessor do to serve the various request in an order to increase the productivity. Big Pipe is totally implemented in PHP and javascript. By loading and rendering the main page structure first with minimal info on it, the page appears to load quicker than having to wait for a complete page to download and then render. To exploit the parallelism between web server and browser, BigPipe first breaks web pages into multiple chunks called pagelets. Just as a  pipelining microprocessor  divides an instruction’s life cycle into multiple stages (such as “instruction fetch”, “instruction decode”, ...
2 comments
Read more