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