Find Closest Value In Bst

Category: Binary Search Trees

```

Problem Statement

(Problem statement not extracted)

```

Approach & Solution

Solution 1

``` Solution 1 Solution 2 class Program { // Average: O(log(n)) time | O(log(n)) space // Worst: O(n) time | O(n) space public static int findClosestValueInBst(BST tree, int target) { return findClosestValueInBst(tree, target, Double.MAX_VALUE); } public static int findClosestValueInBst(BST tree, int target, double closest) { if (Math.abs(target - closest) > Math.abs(target - tree.value)) { closest = tree.value; } if (target < tree.value && tree.left != null) { return findClosestValueInBst(tree.left, target, closest); } else if (target > tree.value && tree.right != null) { return findClosestValueInBst(tree.right, target, closest); } else { return (int) closest; } } static class BST { public int value; public BST left; public BST right; public BST(int value) { this.value = value; } } }

Solution 2

``` Solution 1 Solution 2 2 3 class Program { 4 // Average: O(log(n)) time | O(1) space 5 // Worst: O(n) time | O(1) space 6 public static int findClosestValueInBst(BST tree, int target) { 7 return findClosestValueInBst(tree, target, Double.MAX_VALUE); 8 } 9 10 public static int findClosestValueInBst(BST tree, int target, double closest) { 11 BST currentNode = tree; 12 while (currentNode != null) { 13 if (Math.abs(target - closest) > Math.abs(target - currentNode.value)) { 14 closest = currentNode.value; 15 } 16 if (target < currentNode.value) { 17 currentNode = currentNode.left; 18 } else if (target > currentNode.value) { 19 currentNode = currentNode.right; 20 } else { 21 break; 22 } 23 } 24 return (int) closest; 25 } 26 27 static class BST { 28 public int value; 29 public BST left; 30 public BST right; 31 32 public BST(int value) { 33 this.value = value; 34 } 35 } 36 } 37

```

Test Cases

``` Video Solution Video Solution

Test Case 1 { "tree": { "nodes": [ {"id": "10", "left": "5", "right": "15", "value": 10}, {"id": "15", "left": "13", "right": "22", "value": 15}, {"id": "22", "left": null, "right": null, "value": 22}, {"id": "13", "left": null, "right": "14", "value": 13}, {"id": "14", "left": null, "right": null, "value": 14}, {"id": "5", "left": "2", "right": "5-2", "value": 5}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": null, "value": 2}, {"id": "1", "left": null, "right": null, "value": 1} ], "root": "10" }, "target": 12 } Test Case 2 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right": null, "value": 55000}, {"id": "1001", "left": null, "right": "4500", "value": 1001}, {"id": "4500", "left": null, "right": null, "value": 4500}, {"id": "204", "left": "203", "right": "205", "value": 204}, {"id": "205", "left": null, "right": "207", "value": 205}, {"id": "207", "left": "206", "right": "208", "value": 207}, {"id": "208", "left": null, "right": null, "value": 208}, {"id": "206", "left": null, "right": null, "value": 206}, {"id": "203", "left": null, "right": null, "value": 203}, {"id": "5", "left": "2", "right": "15", "value": 5}, {"id": "15", "left": "5-2", "right": "22", "value": 15}, {"id": "22", "left": null, "right": "57", "value": 22}, {"id": "57", "left": null, "right": "60", "value": 57}, {"id": "60", "left": null, "right": null, "value": 60}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": "3", "value": 2}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "1", "left": "-51", "right": "1-2", "value": 1}, {"id": "1-2", "left": null, "right": "1-3", "value": 1}, {"id": "1-3", "left": null, "right": "1-4", "value": 1}, {"id": "1-4", "left": null, "right": "1-5", "value": 1}, {"id": "1-5", "left": null, "right": null, "value": 1}, {"id": "-51", "left": "-403", "right": null, "value": -51}, {"id": "-403", "left": null, "right": null, "value": -403} ], "root": "100" }, "target": 100 } Test Case 3 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right": null, "value": 55000}, {"id": "1001", "left": null, "right": "4500", "value": 1001}, {"id": "4500", "left": null, "right": null, "value": 4500}, {"id": "204", "left": "203", "right": "205", "value": 204}, {"id": "205", "left": null, "right": "207", "value": 205}, {"id": "207", "left": "206", "right": "208", "value": 207}, {"id": "208", "left": null, "right": null, "value": 208}, {"id": "206", "left": null, "right": null, "value": 206}, {"id": "203", "left": null, "right": null, "value": 203}, {"id": "5", "left": "2", "right": "15", "value": 5}, {"id": "15", "left": "5-2", "right": "22", "value": 15}, {"id": "22", "left": null, "right": "57", "value": 22}, {"id": "57", "left": null, "right": "60", "value": 57}, {"id": "60", "left": null, "right": null, "value": 60}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": "3", "value": 2}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "1", "left": "-51", "right": "1-2", "value": 1}, {"id": "1-2", "left": null, "right": "1-3", "value": 1}, {"id": "1-3", "left": null, "right": "1-4", "value": 1}, {"id": "1-4", "left": null, "right": "1-5", "value": 1}, {"id": "1-5", "left": null, "right": null, "value": 1}, {"id": "-51", "left": "-403", "right": null, "value": -51}, {"id": "-403", "left": null, "right": null, "value": -403} ], "root": "100" }, "target": 208 } Test Case 4 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right": null, "value": 55000}, {"id": "1001", "left": null, "right": "4500", "value": 1001}, {"id": "4500", "left": null, "right": null, "value": 4500}, {"id": "204", "left": "203", "right": "205", "value": 204}, {"id": "205", "left": null, "right": "207", "value": 205}, {"id": "207", "left": "206", "right": "208", "value": 207}, {"id": "208", "left": null, "right": null, "value": 208}, {"id": "206", "left": null, "right": null, "value": 206}, {"id": "203", "left": null, "right": null, "value": 203}, {"id": "5", "left": "2", "right": "15", "value": 5}, {"id": "15", "left": "5-2", "right": "22", "value": 15}, {"id": "22", "left": null, "right": "57", "value": 22}, {"id": "57", "left": null, "right": "60", "value": 57}, {"id": "60", "left": null, "right": null, "value": 60}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": "3", "value": 2}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "1", "left": "-51", "right": "1-2", "value": 1}, {"id": "1-2", "left": null, "right": "1-3", "value": 1}, {"id": "1-3", "left": null, "right": "1-4", "value": 1}, {"id": "1-4", "left": null, "right": "1-5", "value": 1}, {"id": "1-5", "left": null, "right": null, "value": 1}, {"id": "-51", "left": "-403", "right": null, "value": -51}, {"id": "-403", "left": null, "right": null, "value": -403} ], "root": "100" }, "target": 4500 } Test Case 5 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right": null, "value": 55000}, {"id": "1001", "left": null, "right": "4500", "value": 1001}, {"id": "4500", "left": null, "right": null, "value": 4500}, {"id": "204", "left": "203", "right": "205", "value": 204}, {"id": "205", "left": null, "right": "207", "value": 205}, {"id": "207", "left": "206", "right": "208", "value": 207}, {"id": "208", "left": null, "right": null, "value": 208}, {"id": "206", "left": null, "right": null, "value": 206}, {"id": "203", "left": null, "right": null, "value": 203}, {"id": "5", "left": "2", "right": "15", "value": 5}, {"id": "15", "left": "5-2", "right": "22", "value": 15}, {"id": "22", "left": null, "right": "57", "value": 22}, {"id": "57", "left": null, "right": "60", "value": 57}, {"id": "60", "left": null, "right": null, "value": 60}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": "3", "value": 2}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "1", "left": "-51", "right": "1-2", "value": 1}, {"id": "1-2", "left": null, "right": "1-3", "value": 1}, {"id": "1-3", "left": null, "right": "1-4", "value": 1}, {"id": "1-4", "left": null, "right": "1-5", "value": 1}, {"id": "1-5", "left": null, "right": null, "value": 1}, {"id": "-51", "left": "-403", "right": null, "value": -51}, {"id": "-403", "left": null, "right": null, "value": -403} ], "root": "100" }, "target": 4501 } Test Case 6 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right": null, "value": 55000}, {"id": "1001", "left": null, "right": "4500", "value": 1001}, {"id": "4500", "left": null, "right": null, "value": 4500}, {"id": "204", "left": "203", "right": "205", "value": 204}, {"id": "205", "left": null, "right": "207", "value": 205}, {"id": "207", "left": "206", "right": "208", "value": 207}, {"id": "208", "left": null, "right": null, "value": 208}, {"id": "206", "left": null, "right": null, "value": 206}, {"id": "203", "left": null, "right": null, "value": 203}, {"id": "5", "left": "2", "right": "15", "value": 5}, {"id": "15", "left": "5-2", "right": "22", "value": 15}, {"id": "22", "left": null, "right": "57", "value": 22}, {"id": "57", "left": null, "right": "60", "value": 57}, {"id": "60", "left": null, "right": null, "value": 60}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": "3", "value": 2}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "1", "left": "-51", "right": "1-2", "value": 1}, {"id": "1-2", "left": null, "right": "1-3", "value": 1}, {"id": "1-3", "left": null, "right": "1-4", "value": 1}, {"id": "1-4", "left": null, "right": "1-5", "value": 1}, {"id": "1-5", "left": null, "right": null, "value": 1}, {"id": "-51", "left": "-403", "right": null, "value": -51}, {"id": "-403", "left": null, "right": null, "value": -403} ], "root": "100" }, "target": -70 } Test Case 7 { "tree": { "nodes": [ {"id": "100", "left": "5", "right": "502", "value": 100}, {"id": "502", "left": "204", "right": "55000", "value": 502}, {"id": "55000", "left": "1001", "right" ... (test file truncated for display)