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: