Unique BSTs

In this problem, we can recursively form all the unique BST for the range 1 to N.So if we make root as ‘K’ then the left subtree will be constructed by range 1 to K-1. and right subtree as K+1 to N.

So, we will define a recursive function REC(i,j) that will return the list of roots of unique BST formed by numbers in range i to j. So if we make the root node with the value ‘K’.Then the left child will be among the list corresponding to REC(i, K-1) and similarly right child among REC(K+1,j).

At last, we will return the list corresponding to REC(1,’N’).

Algorithm:

• Defining REC(i,j) function:
  • If i > j :
    • No tree can be formed.
    • Return a list having an empty Node.
  • If i == j:
    • Only one value. Only one tree exists.
    • Return [new Node with value as i].
  • Set ‘ANS’ as an empty list.
  • For ‘K’ in range i to j:
    • Set LEFTNODES as REC(i, K-1).
    • Set RIGHTNODES as  REC(K+1,j).
    • For L in LEFTNODES:
      • For R in RIGHTNODES:
        • Set NODE as the new node with value as K.
        • Set NODE’s left child as L.
        • Set NODE’s right child as R.
        • Append NODE to ‘ANS’.
  • Return ‘ANS’
• Return list corresponding to  REC(1, N).
• Return REC(1,N).

As we prepare the recursive tree for Approach 1, we can observe that we are having multiple calls for the same subproblem.

In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each state will be calculated only once.

We will define a 2D array ‘DP’ to store the answers.

Algorithm:

• Defining REC(i,j,DP) function:
  • If i > j :
    • No tree can be formed.
    • Return a list having an empty Node.
  • If i == j:
    • Only one value. Only one tree exists.
    • Return [new Node with value as i].
  • If DP[i][j] is not empty:
    • Return DP[i][j].
  • Set ‘ANS’ as an empty list.
  • For ‘K’ in range i to j:
    • Set LEFTNODES as REC(i, K-1).
    • Set RIGHTNODES as  REC(K+1,j).
    • For L in LEFTNODES:
      • For R in RIGHTNODES:
        • Set NODE as the new node with value as K.
        • Set NODE’s left child as L.
        • Set NODE’s right child as R.
        • Append NODE to ‘ANS’.
  • Set DP[i][j] as ‘ANS’.
  • Return ‘ANS’

• Declare a 2D array of an empty list of size (N+1)*(N+1).
• Return list corresponding to  REC(1, N, DP).
• Return REC(1,N, DP).

In this approach, we will use dynamic programming and find the answer to the problem. We will prepare 2D array of lists of root nodes ‘DP’. We will compute the list DP[i][j] using DP[i][K-1] and DP[K+1][j].

Algorithm:

• Declare a 2D array of empty lists of (N+1)*(N+1).
• For i in range 1 to  N:
  • Append a new node with value i into  DP[i][i].
• Declare ‘EMPTY_NODE’ as an empty list of nodes.
• Append a null node into  ‘EMPTY_NODE’.
• For i in range 1 to N-:
  • For j in range 1 to  N-i:
    • Form list corresponding to DP[ j ][ i+j ].
    • For k in range j to i+j, do the following:
      • If k == j :
        • Set ‘LEFTS’ as EMPTY_NODE
      • Else:
        • Set ‘LEFTS’ as DP[ j ][ k-1 ].
      • If k == j+i :
        • Set ‘RIGHTS’ as EMPTY_NODE
      • Else:
        • Set ‘RIGHTS’ as DP[ k+1 ][ i+j ].
      • For L in LEFTS:
        • For R in RIGHTS:
          • Set NODE as new node with value K.
          • Set left child of NODE as L.
          • Set right child of NODE as R.
          • Append NODE to DP[ j ][ i+j ].
• Return list corresponding to DP[1][ N].