PHPize Online / SQLize Online  /  SQLtest Online

<?php final class Node { public int $key; public ?Node $left = null; public ?Node $right = null; public ?Node $parent = null; public function __construct(int $key) { $this->key = $key; } } final class BinarySearchTree { private Node $root; private int $lookingKey; private ?Node $possibleNode = null; public function findInOrderSuccessor(int $key): Node { $this->lookingKey = $key; $this->possibleNode = null; $this->watch($this->root); return $this->possibleNode; } private function watch(?Node $current): void { if ($current === null) { return; } echo "Current node: $current->key\n"; if ($this->possibleNode === null || $this->isClosetSuccessor($current)) { $this->possibleNode = $current; } $pnk = $this->possibleNode->key; echo "Possible node: $pnk\n\n"; $this->watch($current->right); $this->watch($current->left); } private function isClosetSuccessor(Node $node): bool { return $node->key > $this->lookingKey && ($this->possibleNode->key - $this->lookingKey) > ($node->key - $this->lookingKey); } public function build(): void { $this->root = new Node(20); $this->root->right = new Node(25); $this->root->right->parent = &$this->root; $this->root->left = new Node(9); $this->root->left->parent = &$this->root; $this->root->left->left = new Node(5); $this->root->left->left->parent = &$this->root->left; $this->root->left->right = new Node(12); $this->root->left->right->parent = &$this->root->left; $this->root->left->right->right = new Node(14); $this->root->left->right->right->parent = &$this->root->left->right; $this->root->left->right->left = new Node(11); $this->root->left->right->left->parent = &$this->root->left->right; } } $bst = new BinarySearchTree(); $bst->build(); var_dump($bst->findInOrderSuccessor(9)->key); var_dump($bst->findInOrderSuccessor(14)->key);