Same Bsts
Category: Binary Search Trees
```
Problem Statement
Same BSTs An array of integers is said to represent the Binary Search Tree (BST) obtained by inserting each integer in the array, from left to right, into the BST. Write a function that takes in two arrays of integers and determines whether these arrays represent the same BST. Note that you're not allowed to construct any BSTs in your code. A BST is a Binary Tree that consists only of BST nodes. A node is said to be a valid BST node if and only if it satis es the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null . Sample Input arrayOne = [10, 15, 8, 12, 94, 81, 5, 2, 11] arrayTwo = [10, 8, 5, 15, 2, 12, 11, 94, 81] Sample Output true // both arrays represent the BST below / \ 15 / / \ 12 94 / / / 11 81 Hints Hint 1 You can immediately conclude that the input arrays don't represent the same BST if their rst values aren't equal to each other, since their rst values represent the root of the BST. Similarly, you can conclude this if their lengths are di erent. If their rst values are equal to each other and their lengths are the same, what should your next step be? Hint 2 Given an array of integers, all of the values in the array that are smaller than the rst value in the array are located in the left subtree of the BST that the array represents, and all of the values in the array that are greater than or equal to the rst value in the array are located in the right subtree of the BST that the array represents. Use this fact and Hint #1 to recursively determine whether all subtrees in the BSTs represented by the arrays are equal to each other. Hint 3 Write a recursive function that takes in two arrays of integers. If the rst values of the arrays aren't equal to each other or if the arrays don't have the same length, the arrays don't represent the same BST. If the rst values and lengths are equal to each other, respectively, perform the following actions on both arrays: gather all integers that are smaller than the rst integer; these form a new array that represents the left subtree of the relevant BST; gather all integers that are greater than or equal to the rst integer; these form a new array that represents the right subtree of the relevant BST. Call the recursive function twice: once with the two left-subtree arrays and once with the two right-subtree arrays. Hint 4 Do you actually need to create all of the auxiliary arrays mentioned in Hint #3? Optimal Space & Time Complexity O(n^2) time | O(d) space - where n is the number of nodes in each array, respectively, and d is the depth of the BST that they represent
```
Approach & Solution
Solution 1
```
Solution 1 Solution 2
import java.util.*;
class Program {
// O(n^2) time | O(d) space - where n is the number of
// nodes in each array, respectively, and d is the depth
// of the BST that they represent
public static boolean sameBsts(List
Solution 2
```
Solution 1 Solution 2
2
3 import java.util.*;
4
5 class Program {
6 // O(n^2) time | O(d) space - where n is the number of
7 // nodes in each array, respectively, and d is the depth
8 // of the BST that they represent
9 public static boolean sameBsts(List
Solution 3
```
Solution 1 Solution 2
import java.util.*;
class Program {
// O(n^2) time | O(n^2) space - where n is the number of
// nodes in each array, respectively
public static boolean sameBsts(List
```
Test Cases
``` ▲
``` Test Case 1 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2, 11], "arrayTwo": [10, 8, 5, 15, 2, 12, 11, 94, 81] } Test Case 2 {"arrayOne": [1, 2, 3, 4, 5, 6, 7], "arrayTwo": [1, 2, 3, 4, 5, 6, 7]} Test Case 3 {"arrayOne": [7, 6, 5, 4, 3, 2, 1], "arrayTwo": [7, 6, 5, 4, 3, 2, 1]} Test Case 4 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2], "arrayTwo": [10, 8, 5, 15, 2, 12, 94, 81] } Test Case 5 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2], "arrayTwo": [11, 8, 5, 15, 2, 12, 94, 81] } Test Case 6 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2, -1, 100, 45, 12, 8, -1, 8, 2, -34], "arrayTwo": [10, 8, 5, 15, 2, 12, 94, 81, -1, -1, -34, 8, 2, 8, 12, 45, 100] } Test Case 7 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2, -1, 101, 45, 12, 8, -1, 8, 2, -34], "arrayTwo": [10, 8, 5, 15, 2, 12, 94, 81, -1, -1, -34, 8, 2, 8, 12, 45, 100] } Test Case 8 { "arrayOne": [5, 2, -1, 100, 45, 12, 8, -1, 8, 10, 15, 8, 12, 94, 81, 2, -34], "arrayTwo": [5, 8, 10, 15, 2, 8, 12, 45, 100, 2, 12, 94, 81, -1, -1, -34, 8] } Test Case 9 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2, -1, 100, 45, 12, 9, -1, 8, 2, -34], "arrayTwo": [10, 8, 5, 15, 2, 12, 94, 81, -1, -1, -34, 8, 2, 9, 12, 45, 100] } Test Case 10 {"arrayOne": [1, 2, 3, 4, 5, 6, 7, 8], "arrayTwo": [1, 2, 3, 4, 5, 6, 7]} Test Case 11 {"arrayOne": [7, 6, 5, 4, 3, 2, 1], "arrayTwo": [7, 6, 5, 4, 3, 2, 1, 0]} Test Case 12 { "arrayOne": [10, 15, 8, 12, 94, 81, 5, 2, 10], "arrayTwo": [10, 8, 5, 15, 2, 10, 12, 94, 81] } Test Case 13 { "arrayOne": [50, 76, 81, 23, 23, 23, 657, 56, 12, -1, 3], "arrayTwo": [50, 23, 76, 23, 23, 12, 56, 81, -1, 3, 657] }