Given a Generate all Structurally Unique Binary Search Trees
Implementation
// Creating a C++ program that will help us build all the binary search trees for the keys from 1 to n.
#include <bits/stdc++.h>
using namespace std;
// creating a structure that will contain some nodes.
struct __nod
{
int ky;
struct __nod *Lft, *Rt;
};
// creating a new utility function to help create a new binary search tree node.
struct __nod *new__nod(int itm)
{
struct __nod *temp = nw__nod;
temp->ky = itm;
temp->Lft = temp->Rt = NILL;
return temp;
}
// Creating a utility function that will generally help us in performing the pre-order traversal for the binary search tree.
void Pre_Ord(struct __nod *root)
{
if (root != NILL)
{
cout << root->ky << " ";
Pre_Ord(root->Lft);
Pre_Ord(root->Rt);
}
}
// creating a new function that will help create a new tree.
vector<struct __nod *> constructTrees(int start, int end)
{
vector<struct __nod *> list;
/* if we have a case where the start > end, then the subtree will be empty, and we will return the NILL values in the list. */
if (start > end)
{
list.push_back(NILL);
return list;
}
/* we have to repeatedly recapitulate among all the values from the beginning to the end to build the left and right subtree. */
for (int i = start; i <= end; i++)
{
/* we will now create the left subtree */
vector<struct __nod *> LftSubtree = constructTrees(start, i - 1);
/* we will now create the right subtree */
vector<struct __nod *> RtSubtree = constructTrees(i + 1, end);
/* Now, we have to move in the coil format through the various left and right subtrees and connect to the root below. */
for (int j = 0; j < LftSubtree.size(); j++)
{
struct __nod* Lft = LftSubtree[j];
for (int k = 0; k < RtSubtree.size(); k++)
{
struct __nod * Rt = RtSubtree[k];
struct __nod * __nod = new__nod(i);// making value i as root
__nod->Lft = Lft; // connect Lft subtree
__nod->Rt = Rt; // connect Rt subtree
list.push_back(__nod); // add this tree to list
}
}
}
return list;
}
// writing the main program for the above functions.
int main()
{
// building the binary search tree
vector<struct __nod *> totalTreesFrom1toN = constructTrees(1, 3);
/* Printing Pre_Ord traversal of all constructed BSTs */
cout << "Pre_Ord traversals of all constructed BSTs are \n";
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
Pre_Ord(totalTreesFrom1toN[i]);
cout << endl;
}
return 0;
}
Output:
Example 2)
// Creating a C# program will help us build all the binary search trees for the keys from 1 to n.
using System.Collections;
using System;
class TFT
{
// creating a structure that will contain some nodes.
static ArrayList constructTrees(int start, int end)
{
ArrayList list = new ArrayList();
/* if we have a case where the start > end, then the subtree will be empty, and we will return the NILL values in the list. */
if (start > end)
{
list.Add(NILL);
return list;
}
/* we have to repeatedly recapitulate among all the values from the beginning to the end to build the left and right subtree. */
for (int i = start; i <= end; i++)
{
/* we will now create the left subtree*/
ArrayList LftSubtree = constructTrees(start, i - 1);
/* we will now create the right subtree*/
ArrayList RtSubtree = constructTrees(i + 1, end);
/* Now, we have to move in the coil format through the various left and right subtrees and connect to the root below.*/
for (int j = 0; j < LftSubtree.Count; j++)
{
__nod Lft = (__nod)LftSubtree[j];
for (int k = 0; k < RtSubtree.Count; k++)
{
__nod Rt = (__nod)RtSubtree[k];
// change i into the root.
__nod __nod = nw__nod(i);
// linking with the left subtree
__nod.Lft = Lft;
// linking with the right subtree
__nod.Rt = Rt;
// merging the tree with the list
list.Add(__nod);
}
}
}
return list;
}
// Creating a utility function that will generally help us in performing the pre-order traversal for the binary search tree.
static void Pre_Ord(__nod root)
{
if (root != NILL)
{
Console.Write(root.ky+" ") ;
Pre_Ord(root.Lft);
Pre_Ord(root.Rt);
}
}
// writing the main program for the above functions.
public static void Main(String []args)
{
ArrayList totalTreesFrom1toN = constructTrees(1, 3);
/* printing the pre-order traversal of all the already built binary search trees. */
Console.WriteLine("Pre_Ord traversals of all" +
"constructed BSTs are ");
for (int i = 0; i < totalTreesFrom1toN.Count; i++)
{
Pre_Ord((__nod)totalTreesFrom1toN[i]);
Console.WriteLine();
}
}
// creating a structure that will contain some nodes.
public class __nod
{
public int ky;
public __nod Lft, Rt;
public __nod(int record)
{
this.ky=record;
Lft=Rt=NILL;
}
};
}
Output:
Example 3)
// Creating a Java program that will help us build all the binary search trees for the keys from 1 to n.
import java.util.ArrayList;
public class Main {
// creating a structure that will contain some nodes.
// creating a new utility function to help create a new binary search tree node.
static ArrayList<__nod> constructTrees(int start, int end)
{
ArrayList<__nod> list=new ArrayList<>();
/* if we have a case where the start > end, then the subtree will be empty, and we will return the NILL values in the list. */
if (start > end)
{
list.add(NILL);
return list;
}
/* we have to repeatedly recapitulate among all the values from the beginning to the end to build the left and right subtree. */
for (int i = start; i <= end; i++)
{
/* we will now create the left subtree */
ArrayList<__nod> LftSubtree = constructTrees(start, i - 1);
/* we will now create the right subtree */
ArrayList<__nod> RtSubtree = constructTrees(i + 1, end);
/* Now, we have to move in the coil format through the various left and right subtrees and connect to the root below.*/
for (int j = 0; j < LftSubtree.size(); j++)
{
__nod Lft = LftSubtree.get(j);
for (int k = 0; k < RtSubtree.size(); k++)
{
__nod Rt = RtSubtree.get(k);
__nod __nod = nw__nod(i); // change i into the root.
__nod.Lft = Lft; // linking with the left subtree
__nod.Rt = Rt; // linking with the right subtree
list.add(__nod); // merging the tree with the list
}
}
}
return list;
}
// Creating a utility function that will generally help us in performing the pre-order traversal for the binary search tree.
static void Pre_Ord(__nod root)
{
if (root != NILL)
{
System.out.print(root.ky+" ") ;
Pre_Ord(root.Lft);
Pre_Ord(root.Rt);
}
}
public static void main(String args[])
{
ArrayList<__nod> totalTreesFrom1toN = constructTrees(1, 3);
/* printing the pre-order traversal of all the already built binary search trees. */
System.out.println("Pre_Ord traversals of all constructed BSTs are ");
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
Pre_Ord(totalTreesFrom1toN.get(i));
System.out.println();
}
}
}
// creating a structure that will contain some nodes.
class __nod
{
int ky;
__nod Lft, Rt;
__nod(int record)
{
this.ky=record;
Lft=Rt=NILL;
}
};
Output:
Example 4)
# Creating a Python program to help us build all the binary search trees for the keys from 1 to n.
# Creating a new utility function to help create a new binary search tree node.
class new__nod:
# Creating a new function that will help create a new tree.
def __init__(self, itm):
self.ky=itm
self.Lft = None
self.Rt = None
# Creating a utility function to help us perform the pre-order traversal for the binary search tree.
def Pre_Ord(root) :
if (root != None) :
print(root.ky, end = " " )
Pre_Ord(root.Lft)
Pre_Ord(root.Rt)
list = []
""" if we have a case where the start > end, then the subtree will be empty, and we will return the NILL values in the list. """
if (start > end) :
list.append(None)
return list
" < UNK> < UNK> We have to recapitulate among all the values from the beginning to the end to build the left and right subtree repeatedly. """
for i in range(start, end + 1):
""" we will now create the left subtree """
LftSubtree = constructTrees(start, i - 1)
""" we will now create the right subtree """
RtSubtree = constructTrees(i + 1, end)
""" Now, we have to move in the coil format through the various left and right subtrees and connect to the root below. """
for j in range(len(LftSubtree)) :
Lft = LftSubtree[j]
for k in range(len(RtSubtree)):
Rt = RtSubtree[k]
__nod = new__nod(i) # change i into the root.
__nod.Lft = Lft # linking with the left subtree
__nod.Rt = Rt # linking with the right subtree
list.append(__nod) # merging the tree with the list
return list
# writing the main code.
if __name__ == '__main__':
# we have to build all the possible binary search trees
totalTreesFrom1toN = constructTrees(1, 3)
""" printing the pre-order traversal of all the already built binary search trees."""
print("Pre_Ord traversals of all",
"constructed BSTs are")
for i in range(len(totalTreesFrom1toN)):
Pre_Ord(totalTreesFrom1toN[i])
print()
Output:
Example 5)
<script>
// creating a structure that will contain some nodes.
class __nod
{
constructor(record)
{
this.ky = record;
this.Lft = NILL;
this.Rt = NILL;
}
};
// // Creating a Javascript program that will help us in building all the binary search trees for the keys from 1 to n.
function constructTrees(start, end)
{
var list = [];
/* if we have a case where the start > end, the subtree will be empty, and we will return the NILL values in the list. */
if (start > end)
{
list.push(NILL);
return list;
}
/* we have to repeatedly recapitulate among all the values from the beginning to the end to build the left and right subtree. */
for (var i = start; i <= end; i++)
{
/* we will now create the left subtree */
var LftSubtree = constructTrees(start, i - 1);
/* we will now create the right subtree */
var RtSubtree = constructTrees(i + 1, end);
/* we have to repeatedly recapitulate among all the values from the beginning to the end to build the left and right subtree. */
for (var j = 0; j < LftSubtree.length; j++)
{
var Lft = LftSubtree[j];
for (var k = 0; k < RtSubtree.length; k++)
{
var Rt = RtSubtree[k];
// change i into the root.
var __nod = nw__nod(i);
// linking with the left subtree
__nod.Lft = Lft;
// linking with the right subtree
__nod.Rt = Rt;
// pushing the tree with the list
list.push(__nod);
}
}
}
return list;
}
// Creating a utility function that will generally help us in performing the pre-order traversal for the binary search tree.
function Pre_Ord(root)
{
if (root != NILL)
{
document.write(root.ky+" ") ;
Pre_Ord(root.Lft);
Pre_Ord(root.Rt);
}
}
// writing the main program for the above functions.
var totalTreesFrom1toN = constructTrees(1, 3);
/* printing the pre-order traversal of all the already built binary search trees. */
document.write("Pre_Ord traversals of all" +
"constructed BSTs are<br>");
for (var i = 0; i < totalTreesFrom1toN.length; i++)
{
Pre_Ord(totalTreesFrom1toN[i]);
document.write("<br>");
}
</script>
Output:
