Construct all possible BSTs for keys 1 to N - GeeksforGeeks
count of possible BST (Binary Search Trees)s is discussed, then construction of all possible BSTs.
Read full article from Construct all possible BSTs for keys 1 to N - GeeksforGeeks
count of possible BST (Binary Search Trees)s is discussed, then construction of all possible BSTs.
How to construct all BST for keys 1..N?
The idea is to maintain a list of roots of all BSTs. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.
The idea is to maintain a list of roots of all BSTs. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.
1) Initialize list of BSTs as empty. 2) For every number i where i varies from 1 to N, do following ......a) Create a new node with key as 'i', let this node be 'node' ......b) Recursively construct list of all left subtrees. ......c) Recursively construct list of all right subtrees. 3) Iterate for all left subtrees a) For current leftsubtree, iterate for all right subtrees Add current left and right subtrees to 'node' and add 'node' to list.
vector<
struct
node *> constructTrees(
int
start,
int
end)
{
vector<
struct
node *> list;
/* if start > end then subtree will be empty so returning NULL
in the list */
if
(start > end)
{
list.push_back(NULL);
return
list;
}
/* iterating through all values from start to end for constructing\
left and right subtree recursively */
for
(
int
i = start; i <= end; i++)
{
/* constructing left subtree */
vector<
struct
node *> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
vector<
struct
node *> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting
them to ith root below */
for
(
int
j = 0; j < leftSubtree.size(); j++)
{
struct
node* left = leftSubtree[j];
for
(
int
k = 0; k < rightSubtree.size(); k++)
{
struct
node * right = rightSubtree[k];
struct
node * node = newNode(i);
// making value i as root
node->left = left;
// connect left subtree
node->right = right;
// connect right subtree
list.push_back(node);
// add this tree to list
}
}
}
return
list;
}
Read full article from Construct all possible BSTs for keys 1 to N - GeeksforGeeks