PHPize Online / SQLize Online  /  SQLtest Online

A A A
Share      Blog   Popular
Copy Format Clear
Copy Clear
Copy Format Clear
<?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->watch($this->root); return $this->possibleNode; } private function watch(?Node $current): void { if ($current === null) { return; } echo "Current node: $current->key\n"; if ($this->isClosetSuccessor($current)) { $this->possibleNode = $current; } $this->watch($current->right); $this->watch($current->left); } private function isClosetSuccessor(Node $node): bool { if ($this->possibleNode) { echo var_export(($this->possibleNode->key - $this->lookingKey) > ($node->key - $this->lookingKey)) . PHP_EOL; } return $this->possibleNode === null || ($node->key > $this->lookingKey && $node->key <= $this->possibleNode->key); } 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);
Show:  
Copy Clear