node.php

<?hh // strict

class Node {
  private int $value;
  public ?Node $left = null;
  public ?Node $right = null;

  public function __construct(int $value) {
    $this->value = $value;
  }

  public static function fromArrayToBST(array<int> $arr): ?Node {
    if ($arr === []) {
      return null;
    }
    $mid = intdiv(count($arr), 2);
    $n = new Node($arr[$mid]);
    $n->left = self::fromArrayToBST(array_slice($arr, 0, $mid));
    $n->right = self::fromArrayToBST(array_slice($arr, $mid + 1));

    return $n;
  }

  public function getValue(): int {
    return $this->value;
  }
}

class BSTToDoublyLinkedList {
  public static function convert(?Node $root): ?Node {
    if ($root === null) {
      return $root;
    }

    if ($root && $root->left !== null) {
      $left = self::convert($root?->left);
      if ($left) {
        // make left point to predecessor
        while ($left->right !== null) {
          $left = $left->right;
        }

        $left->right = $root;
        $root->left = $left;
      }
    }

    if ($root && $root->right !== null) {
      $right = self::convert($root?->right);

      if ($right) {
        // make right point to successor
        while ($right->left !== null) {
          $right = $right->left;
        }

        $right->left = $root;
        $root->right = $right;
      }
    }
    return $root;
  }

  public static function print(Node $node): void {
    if ($node->left) {
      self::print($node->left);
    }

    echo "{$node->getValue()} ";

    if ($node->right) {
      self::print($node->right);
    }
  }

}