Same BSTs

Tags

Same BSTs

Category

Binary Search Trees (BST)

Difficulty

Medium

Problem Statement

Given two arrays of distinct integers, determine whether the two arrays would produce the same Binary Search Tree (BST) if each array's elements were inserted in order (from left to right) into an initially empty BST. You must solve this without actually constructing either BST.

Intuition

Two arrays produce the same BST if and only if they share the same root and, recursively, the same left and right subtrees. The first element of each array is the root of the BST. All elements smaller than the root will be inserted into the left subtree, and all elements larger will go into the right subtree. Crucially, the relative order of elements within each group (smaller or larger) must be preserved and must match between the two arrays.

By recursively partitioning both arrays into "left subtree elements" and "right subtree elements" (preserving relative order) and comparing them, we can determine equivalence without building any tree.

Approach

  1. If the two arrays have different lengths, return false.
  2. If both arrays are empty, return true.
  3. If the first elements (roots) differ, return false.
  4. Partition each array into two sub-arrays:
    • Elements smaller than the root (preserving relative order).
    • Elements greater than or equal to the root (preserving relative order, excluding the root itself).
  5. Recursively check that both the "smaller" sub-arrays represent the same BST and both the "larger" sub-arrays represent the same BST.

Pseudocode

function sameBSTs(arrayOne, arrayTwo):
    if length(arrayOne) != length(arrayTwo):
        return false
    if length(arrayOne) == 0:
        return true
    if arrayOne[0] != arrayTwo[0]:
        return false

    leftOne = elements in arrayOne[1:] that are < arrayOne[0]
    rightOne = elements in arrayOne[1:] that are >= arrayOne[0]
    leftTwo = elements in arrayTwo[1:] that are < arrayTwo[0]
    rightTwo = elements in arrayTwo[1:] that are >= arrayTwo[0]

    return sameBSTs(leftOne, leftTwo) and sameBSTs(rightOne, rightTwo)

Time & Space Complexity

  • Time: O(n^2) in the worst case, where n is the number of elements. At each recursive level, we scan through the arrays to partition them. In the worst case (sorted array), this gives n levels of O(n) work each.
  • Space: O(n^2) in the worst case due to creating new sub-arrays at each recursive level. This can be optimized to O(n) space by using index tracking instead of creating new arrays, though with the same O(n^2) time.

Key Insights

  • The first element always determines the root, and the BST property determines the partition.
  • Relative order within each partition matters because it dictates the structure of the subtree.
  • You do not need to build the tree; the recursive partition comparison is sufficient.
  • An O(n^2) time, O(d) space solution (where d is the depth) exists by passing indices instead of creating sub-arrays, but it is more complex to implement.

Edge Cases

  • Both arrays are empty: return true.
  • Arrays of length 1 with the same value: return true.
  • Arrays of length 1 with different values: return false.
  • Arrays with the same elements but different first elements: return false (different roots mean different BSTs).
  • Sorted arrays: worst-case scenario for time complexity, as each partition only removes the root.

Linked mentions