Unival - PHP Online

Form of PHP Sandbox

Enter Your PHP code here for testing/debugging in the Online PHP Sandbox. As in the usual PHP files, you can also add HTML, but do not forget to add the tag <?php in the places where the PHP script should be executed.



Your result can be seen below.

Result of php executing





Full code of Unival.php

  1. <?php
  2.  
  3. class Node {
  4.     private $children;
  5.     private $value;
  6.     
  7.     public function value() {
  8.         return $this->value;
  9.     }
  10.     
  11.     public function __construct($value) {
  12.         $this->value = $value;
  13.         $this->children = [];
  14.     }
  15.     
  16.     /**
  17.      * @returns Node[]
  18.      */
  19.     public function children() {
  20.         return $this->children;
  21.     }
  22.     
  23.     /**
  24.      * @param   Node $child
  25.      * @returns void
  26.      */
  27.     public function addChild($child) {
  28.         $this->children[] = $child;
  29.     }
  30. }
  31.  
  32. class UnivalUtils {
  33.     /** 
  34.      * @param   Node $node
  35.      * @returns bool
  36.      */
  37.     public static function isUnival($node) {
  38.         // Empty tree is considered unival
  39.         if ($node === null) {
  40.             return true;
  41.         }
  42.         
  43.         // Leaf node: wind the recursion upwards from here starting at true
  44.         if (empty($node->children())) {
  45.             return true;
  46.         }
  47.         
  48.         $isUnival = true;
  49.         foreach ($node->children() as $child) {
  50.             $isUnival =
  51.                 $isUnival
  52.                 && ($node->value() === $child->value())
  53.                 && self::isUnival($child);
  54.         }
  55.         
  56.         return $isUnival;
  57.     }
  58.     
  59.     /**
  60.      * @param   Node $node
  61.      * @returns int
  62.      */
  63.     public static function countUnivalSubtrees($node) {
  64.         // Base case: null $node, return 1 b/c null tree is considered Unival
  65.         if ($node === null) {
  66.             return 1;
  67.         }
  68.         
  69.         // Base case: leaf node, return 1 b/c each leaf is its own Unival tree
  70.         if (empty($node->children())) {
  71.             return 1;
  72.         }
  73.         
  74.         $univalSubtreesCount = 0;
  75.         foreach ($node->children() as $child) {
  76.             if (self::isUnival($child)) {
  77.                 $univalSubtreesCount += self::countUnivalSubtrees($child);
  78.             }
  79.         }
  80.         
  81.         if (self::isUnival($node)) {
  82.             $univalSubtreesCount++;
  83.         }
  84.         
  85.         return $univalSubtreesCount;
  86.     }
  87. }
  88.  
  89. /**
  90.  *               3
  91.  *    3          3          3
  92.  * 3     3    3     3    3     3
  93.  */
  94. $root = new Node(3);
  95. $rootChild1 = new Node(3);
  96. $rootChild1Child1 = new Node(3);
  97. $rootChild1Child2 = new Node(3);
  98. $rootChild1->addChild($rootChild1Child1);
  99. $rootChild1->addChild($rootChild1Child2);
  100. $root->addChild($rootChild1);
  101.  
  102. $rootChild2 = new Node(3);
  103. $rootChild2Child1 = new Node(3);
  104. $rootChild2Child2 = new Node(3);
  105. $rootChild2->addChild($rootChild2Child1);
  106. $rootChild2->addChild($rootChild2Child2);
  107. $root->addChild($rootChild2);
  108.  
  109. $rootChild3 = new Node(3);
  110. $rootChild3Child1 = new Node(3);
  111. $rootChild3Child2 = new Node(3);
  112. $rootChild3->addChild($rootChild3Child1);
  113. $rootChild3->addChild($rootChild3Child2);
  114. $root->addChild($rootChild3);
  115.  
  116. print_r('Number of Unival subtrees found in Tree: ' . UnivalUtils::countUnivalSubtrees($root));
File Description
  • Unival
  • PHP Code
  • 29 Jan-2020
  • 2.76 Kb
You can Share it: