CODEWITHSUNDEEP
algorithm
wjmolina
wjmolina

Reputation: 2675

Generating All Binary Search Trees from 1 to n

I ran into the following problem:

Given a positive integer n, generate all binary search trees with nodes 1, 2, ..., n.

For example, given 3, one obtains:

                                   enter image description here

I am doing the following:

Generate all the permutations of the sequence (1, 2, ..., n).
For each permutation p:
    Create a tree t.
    For each number n in p:
        Insert n into t.
    If t has not yet been generated, keep it. <-- Expensive Operation

However, this approach is slow because duplicate trees are generated (for n = 3, (2, 1, 3) and (2, 3, 1) generate the same tree), and I need to ensure they are not kept. Would someone point me toward a faster approach?

Upvotes: 2

Views: 3204

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is pseudo code to do it without duplicates(But u would still need lots of space because no of tree generate is high).

TreeList void genAllBST(int high,int low) {

  if(high>=low) {
      currList = []
      for(int i=low;i<=high;i++) {
          curr = new Node(i);
          leftList = genAllBST(i-1,low);
          rightList = genAllBST(high,i+1);
          TreeList c = connect(curr,leftList,rightList);  
          currList.add(c);
      }

     return(currList);

  }

   return(null);
}

genAllBST(n,1);

Upvotes: 5

Related Questions