Bst Construction

Category: Binary Search Trees

```

Problem Statement

Sample Usage // Assume the following BST has already been created: / \ 15 / \ / \ 5 13 22 / \ 14 // All operations below are performed sequentially. insert(12): 10 / \ 15 / \ / \ 5 13 22 / / \ 12 14 remove(10): 12 / \ 15 / \ / \ 5 13 22 / \ 14 contains(15): true Hints Hint 1 As you try to insert, nd, or a remove a value into, in, or from a BST, you will have to traverse the tree's nodes. The BST property allows you to eliminate half of the remaining tree at each node that you traverse: if the target value is strictly smaller than a node's value, then it must be (or can only be) located to the left of the node, otherwise it must be (or can only be) to the right of that node. Hint 2 Traverse the BST all the while applying the logic described in Hint #1. For insertion, add the target value to the BST once you reach a leaf (None / null) node. For searching, if you reach a leaf node without having found the target value that means the value isn't in the BST. For removal, consider the various cases that you might encounter: the node you need to remove might have two children nodes, one, or none; it might also be the root node; make sure to account for all of these cases. Hint 3 What are the advantages and disadvantages of implementing these methods iteratively as opposed to recursively? Optimal Space & Time Complexity Average (all 3 methods): O(log(n)) time | O(1) space - where n is the number of nodes in the BST Worst (all 3 methods): O(n) time | O(1) space - where n is the number of nodes in the BST

```

Approach & Solution

Solution 1

``` Solution 1 Solution 2 return false; } // Average: O(log(n)) time | O(1) space // Worst: O(n) time | O(1) space public BST remove(int value) { remove(value, null); return this; } public void remove(int value, BST parentNode) { BST currentNode = this; while (currentNode != null) { if (value < currentNode.value) { parentNode = currentNode; currentNode = currentNode.left; } else if (value > currentNode.value) { parentNode = currentNode; currentNode = currentNode.right; } else { if (currentNode.left != null && currentNode.right != null) { currentNode.value = currentNode.right.getMinValue(); currentNode.right.remove(currentNode.value, currentNode); } else if (parentNode == null) { if (currentNode.left != null) { currentNode.value = currentNode.left.value; currentNode.right = currentNode.left.right; currentNode.left = currentNode.left.left; i i } else if (currentNode.right != null) { currentNode.value = currentNode.right.value; currentNode.left = currentNode.right.left; currentNode.right = currentNode.right.right; } else { // This is a single-node tree; do nothing. } } else if (parentNode.left == currentNode) { parentNode.left = currentNode.left != null ? currentNode.left : currentNode.right; } else if (parentNode.right == currentNode) { parentNode.right = currentNode.left != null ? currentNode.left : currentNode.right; } break; } } } public int getMinValue() { if (left == null) { return value; } else { return left.getMinValue(); } } } }

Solution 2

``` Solution 1 Solution 2 2 3 class Program { 4 static class BST { 5 public int value; 6 public BST left; 7 public BST right; 8 9 public BST(int value) { 10 this.value = value; 11 } 12 13 // Average: O(log(n)) time | O(1) space 14 // Worst: O(n) time | O(1) space 15 public BST insert(int value) { 16 BST currentNode = this; 17 while (true) { 18 if (value < currentNode.value) { 19 if (currentNode.left == null) { 20 BST newNode = new BST(value); 21 currentNode.left = newNode; 22 break; 23 } else { 24 currentNode = currentNode.left; 25 } 26 } else { 27 if (currentNode.right == null) { 28 BST newNode = new BST(value); 29 currentNode.right = newNode; 30 break; 31 } else { 32 currentNode = currentNode.right; 33 } 34 } 35 } 36 return this; 37 } 38 39 // Average: O(log(n)) time | O(1) space 40 // Worst: O(n) time | O(1) space 41 public boolean contains(int value) { 42 BST currentNode = this; 43 while (currentNode != null) { 44 if (value < currentNode.value) { 45 currentNode = currentNode.left; 46 } else if (value > currentNode.value) { 47 currentNode = currentNode.right; 48 } else { 49 return true;

Solution 3

``` Solution 1 Solution 2 remove(value, null); return this; } public void remove(int value, BST parent) { if (value < this.value) { if (left != null) { left.remove(value, this); } } else if (value > this.value) { if (right != null) { right.remove(value, this); } } else { if (left != null && right != null) { this.value = right.getMinValue(); right.remove(this.value, this); } else if (parent == null) { if (left != null) { this.value = left.value; this.value left.value; right = left.right; left = left.left; } else if (right != null) { this.value = right.value; left = right.left; right = right.right; } else { // This is a single-node tree; do nothing. } } else if (parent.left == this) { parent.left = left != null ? left : right; } else if (parent.right == this) { parent.right = left != null ? left : right; } } } public int getMinValue() { if (left == null) { return this.value; } else { return left.getMinValue(); } } } }

Solution 4

``` Solution 1 Solution 2 2 3 class Program { 4 static class BST { 5 public int value; 6 public BST left; 7 public BST right; 8 9 public BST(int value) { 10 this.value = value; 11 } 12 13 // Average: O(log(n)) time | O(log(n)) space 14 // Worst: O(n) time | O(n) space 15 public BST insert(int value) { 16 if (value < this.value) { 17 if (left == null) { 18 BST newBST = new BST(value); 19 left = newBST; 20 } else { 21 left.insert(value); 22 } 23 } else { 24 if (right == null) { 25 BST newBST = new BST(value); 26 right = newBST; 27 } else { 28 right.insert(value); 29 } 30 } 31 return this; 32 } 33 34 // Average: O(log(n)) time | O(log(n)) space 35 // Worst: O(n) time | O(n) space 36 public boolean contains(int value) { 37 if (value < this.value) { 38 if (left == null) { 39 return false; 40 } else { 41 return left.contains(value); 42 } 43 } else if (value > this.value) { 44 if (right == null) { 45 return false; 46 } else { 47 return right.contains(value); 48 } 49 } else { 50 return true; 51 } 52 } 53 54 // Average: O(log(n)) time | O(log(n)) space 55 // Worst: O(n) time | O(n) space 56 public BST remove(int value) { 57 remove(value, null); 58 return this; 59 } 60 61 public void remove(int value, BST parent) { 62 if (value < this.value) { 63 if (left != null) { 64 left.remove(value, this); 65 } 66 } else if (value > this.value) { 67 if (right != null) { 68 right.remove(value, this); 69 } 70 } else { 71 if (left != null && right != null) { 72 this.value = right.getMinValue(); 73 right.remove(this.value, this); 74 } else if (parent == null) {

```

Test Cases

``` Video Solution

▲ 1 2 ​ 3 class Program { 4 static class BST { 5 public int value; 6 public BST left; 7 public BST right; 8 ​ 9 public BST(int value) { 10 this.value = value; 11 } 12 ​ 13 // Average: O(log(n)) time | O(log(n)) space 14 // Worst: O(n) time | O(n) space 15 public BST insert(int value) { 16 if (value < this.value) { 17 if (left == null) { 18 BST newBST = new BST(value); 19 left = newBST; 20 } else { 21 left.insert(value); 22 } 23 } else { 24 if (right == null) { 25 BST newBST = new BST(value); 26 right = newBST; 27 } else { 28 right.insert(value); 29 } 30 } 31 return this; 32 } 33 ​ 34 // Average: O(log(n)) time | O(log(n)) space 35 // Worst: O(n) time | O(n) space 36 public boolean contains(int value) { 37 if (value < this.value) { 38 if (left == null) { 39 return false; 40 } else { 41 return left.contains(value); 42 } 43 } else if (value > this.value) { 44 if (right == null) { 45 return false;

``` Test Case 1 { "rootValue": 10, "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [15], "method": "insert"}, {"arguments": [2], "method": "insert"}, {"arguments": [5], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [22], "method": "insert"}, {"arguments": [1], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [12], "method": "insert"}, {"arguments": [10], "method": "remove"}, {"arguments": [15], "method": "contains"} ] } Test Case 2 { "rootValue": 10, "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [15], "method": "insert"} ] } Test Case 3 { "rootValue": 10, "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [15], "method": "insert"}, {"arguments": [10], "method": "contains"}, {"arguments": [5], "method": "contains"}, {"arguments": [15], "method": "contains"}, {"arguments": [1], "method": "contains"}, {"arguments": [6], "method": "contains"}, {"arguments": [11], "method": "contains"}, {"arguments": [16], "method": "contains"} ] } Test Case 4 { "rootValue": 10, "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [15], "method": "insert"}, {"arguments": [5], "method": "remove"}, {"arguments": [15], "method": "remove"}, {"arguments": [10], "method": "remove"} ] } Test Case 5 { "rootValue": 10, "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [15], "method": "insert"}, {"arguments": [10], "method": "contains"}, {"arguments": [5], "method": "contains"}, {"arguments": [15], "method": "contains"}, {"arguments": [10], "method": "remove"}, {"arguments": [5], "method": "remove"}, {"arguments": [15], "method": "remove"}, {"arguments": [10], "method": "contains"}, {"arguments": [5], "method": "contains"}, {"arguments": [15], "method": "contains"} ] } Test Case 6 { "rootValue": 1, "classMethodsToCall": [ {"arguments": [2], "method": "insert"}, {"arguments": [3], "method": "insert"}, {"arguments": [4], "method": "insert"}, {"arguments": [5], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [7], "method": "insert"}, {"arguments": [8], "method": "insert"}, {"arguments": [9], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [11], "method": "insert"}, {"arguments": [12], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [15], "method": "insert"}, {"arguments": [16], "method": "insert"}, {"arguments": [17], "method": "insert"}, {"arguments": [18], "method": "insert"}, {"arguments": [19], "method": "insert"}, {"arguments": [20], "method": "insert"}, {"arguments": [2], "method": "remove"}, {"arguments": [4], "method": "remove"}, {"arguments": [6], "method": "remove"}, {"arguments": [8], "method": "remove"}, {"arguments": [11], "method": "remove"}, {"arguments": [13], "method": "remove"}, {"arguments": [15], "method": "remove"}, {"arguments": [17], "method": "remove"}, {"arguments": [19], "method": "remove"}, {"arguments": [1], "method": "insert"}, {"arguments": [2], "method": "insert"}, {"arguments": [3], "method": "insert"}, {"arguments": [4], "method": "insert"}, {"arguments": [5], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [7], "method": "insert"}, {"arguments": [8], "method": "insert"}, {"arguments": [9], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [9000], "method": "contains"} ] }