| 1 | class BST { |
| 2 | constructor(value) { |
| 3 | this.value = value; |
| 4 | this.left = null; |
| 5 | this.right = null; |
| 6 | } |
| 7 | |
| 8 | // Time O(log n) |
| 9 | // Space O(1) because we are doing the iteration solution |
| 10 | insert(value) { |
| 11 | let currentNode = this; |
| 12 | while (true) { |
| 13 | if (value < currentNode.value) { |
| 14 | if (currentNode.left === null) { |
| 15 | currentNode.left = new BST(value); |
| 16 | break; |
| 17 | } else { |
| 18 | currentNode = currentNode.left; |
| 19 | } |
| 20 | } else { |
| 21 | if (currentNode.right === null) { |
| 22 | currentNode.right = new BST(value); |
| 23 | break; |
| 24 | } else { |
| 25 | currentNode = currentNode.right; |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | return this; |
| 30 | } |
| 31 | |
| 32 | // Time O(log n) |
| 33 | // Space O(1) because we are doing the iteration solution |
| 34 | contains(value) { |
| 35 | let currentNode = this; |
| 36 | while (currentNode !== null) { |
| 37 | if (value < currentNode.value) { |
| 38 | currentNode = currentNode.left; |
| 39 | } else if (value > currentNode.value) { |
| 40 | currentNode = currentNode.right; |
| 41 | } else { |
| 42 | return true; |
| 43 | } |
| 44 | } |
| 45 | return false; |
| 46 | } |
| 47 | |
| 48 | // Time O(log n) |
| 49 | // Space O(1) because we are doing the iteration solution |
| 50 | remove(value, parentNode = null) { |
| 51 | let currentNode = this; |
| 52 | while (currentNode !== null) { |
| 53 | if (value < currentNode.value) { |
| 54 | parentNode = currentNode; |
| 55 | currentNode = currentNode.left; |
| 56 | } else if (value > currentNode.value) { |
| 57 | parentNode = currentNode; |
| 58 | currentNode = currentNode.right; |
| 59 | } else { |
| 60 | if (currentNode.left !== null && currentNode.right !== null) { |
nothing calls this directly
no outgoing calls
no test coverage detected