Skip to content

1569. Number of Ways to Reorder Array to Get Same BST

Problem

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

  • For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10**9 + 7.

Solution

My sane approach: Dynamic programming and some minor math

Cost me so much time, but here is step by step rundown:

1. Set up BTS tree, for better feel of the problem

Nothing too fancy here, as the problem told:

construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST

class BinarySearchTree:
    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
        self.totalNode = 1
        self.countWayCache = None
        if self.left != None:
            self.totalNode += self.left.totalNode
        if self.right != None:
            self.totalNode += self.right.totalNode

    def addNode(self, value):
        if self.value > value:
            if self.right == None:
                self.right = BinarySearchTree(value)
            else:
                self.right.addNode(value)

        if self.value < value:
            if self.left == None:
                self.left = BinarySearchTree(value)
            else:
                self.left.addNode(value)

        self.totalNode += 1

    def countWays(self, dp, modulo):
        if self.countWayCache != None:
            return self.countWayCache
        totalWay = 1
        if self.left == None and self.right == None:
            return totalWay
        if self.left == None:
            return self.right.countWays(dp, modulo)
        if self.right == None:
            return self.left.countWays(dp, modulo)

        totalWay = self.right.countWays(dp, modulo) * self.left.countWays(dp, modulo) * dp[self.left.totalNode][self.right.totalNode] % modulo
        self.countWayCache = totalWay
        return totalWay

As you see, __init__() and addNode(self, value) does exactly what the problem told. Where I try to cache totalNode on the tree and countWayCache which is the number of different ways to construct the tree for later used as we will want to keep reuse them to deal with the main problem.

Also, I code toDict, toString and interator to debug if I done the BTS implement right

class BinarySearchTree:
    def toDict(self, nestedlevel = None):
        nextNestedLevel = nestedlevel
        if nestedlevel != None:
            nextNestedLevel = nestedlevel - 1
            if nextNestedLevel < 0:
                return "..."

        dictSeft = {}
        dictSeft["value"] = self.value
        if self.left != None:
            dictSeft["left"] = self.left.toDict(nextNestedLevel)
        if self.right != None:
            dictSeft["right"] = self.right.toDict(nextNestedLevel)
        return dictSeft

    def toString(self, nestedlevel = None, indent = 4):
        dictSeft = self.toDict(nestedlevel)
        stringSeft = json.dumps(dictSeft, indent = indent)
        return stringSeft

    def interator(self): 
        nodes = []
        nodes.append(self)
        if self.left != None:
            nodes.append(*self.left.interator())
        if self.right != None:
            nodes.append(*self.right.interator())
        return nodes

Implement countWay(dp, modulo) directly onto BTS tree

Where I try to cache totalNode on the tree and countWayCache which is the number of different ways to construct the tree for later used as we will want to keep reuse them to deal with the main problem.

This is what I staged before, trying to implement countWay(dp, modulo) is a bit tricky, but by some analyzing we know that:

  1. If we already done calculate countWays of a Tree, we can simply return the cache result
  2. If there is neither left nor right node, we can only have 1 way to constructed BST
  3. If there is either left or right node, the root node can’t be change, so we can could return left.countWay(dp, modulo) or right.countWay(dp, modulo) node
  4. The main focus: When both left, right are available.

Quick reference to what we have pre-calculated variable available for use:

  • left.countWay(dp, modulo) , right.countWay(dp, modulo) as leaf node will be in the case 2 or 3
  • left.totalNode , right.totalNode as we keep tracking of them while crafting the BTS tree
  • module is just 10**9 + 7 as the problem staged
  • What left, is dp

What is DP ?

After a lot of paper thinking, I translate this to a new problem: “With two array A and B with n and m length, count how many way to merge them with out changing their element order (Knowing all element is unique)”.

Or similar “With two string A and B, count how many way to merge them with out changing their character order (Knowing each character is unique)”

This could be solving using dynamic programing: dp[i][j] is the number of way to merge an i length array to an j length array with out changing their element order

  1. We always have dp[<any>][0] = dp[0][<any>] = 1 as there is only one way to merge an array with 0 length to another
  2. We also have dp[i][j] = dp[i-1][j] + dp[i][j-1]. As if we try to add a A[i] or B[j] element into the end of ?? 
class BinarySearchTree:
    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
        self.totalNode = 1
        self.countWayCache = None
        if self.left != None:
            self.totalNode += self.left.totalNode
        if self.right != None:
            self.totalNode += self.right.totalNode

    def addNode(self, value):
        if self.value > value:
            if self.right == None:
                self.right = BinarySearchTree(value)
            else:
                self.right.addNode(value)

        if self.value < value:
            if self.left == None:
                self.left = BinarySearchTree(value)
            else:
                self.left.addNode(value)

        self.totalNode += 1

    def countWays(self, dp, modulo):
        if self.countWayCache != None:
            return self.countWayCache
        totalWay = 1
        if self.left == None and self.right == None:
            return totalWay
        if self.left == None:
            return self.right.countWays(dp, modulo)
        if self.right == None:
            return self.left.countWays(dp, modulo)

        totalWay = self.right.countWays(dp, modulo) * self.left.countWays(dp, modulo) * dp[self.left.totalNode][self.right.totalNode] % modulo
        self.countWayCache = totalWay
        return totalWay

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        MODULO = 10**9 + 7
        root = None
        for n in nums:
            if root == None:
                root = BinarySearchTree(n)
            else:
                root.addNode(n)
        dp = [[0]*(len(nums) + 1) for i in range(len(nums) + 1)]

        for i in range(len(nums)+1):
            dp[i][0] = 1
            dp[0][i] = 1
        for i in range(1, len(nums)+1):
            for j in range(1, len(nums)+1):
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MODULO

        totalWays = root.countWays(dp, MODULO)
        return totalWays - 1
Last update : October 13, 2023
Created : August 16, 2023