Came across this question in an interview. Given inorder traversal of a binary tree. Print all the possible binary trees from it.
Initial thought:
If say we have only 2 elements in the array. Say 2,1. Then two possible trees are
2
\
1
1
/
2
If 3 elements Say, 2,1,4. Then we have 5 possible trees.
2 1 4 2 4
\ / \ / \ /
1 2 4 1 4 2
\ / / \
4 2 1 1
So, basically if we have n elements, then we have n-1 branches (childs, / or ). We can arrange these n-1 branches in any order. For n=3, n-1 = 2. So, we have 2 branches. We can arrange the 2 branches in these ways:
/ \ \ / /\
/ \ / \
Initial attempt:
struct node *findTree(int *A,int l,int h)
{
node *root = NULL;
if(h < l)
return NULL;
for(int i=l;i<h;i++)
{
root = newNode(A[i]);
root->left = findTree(A,l,i-1);
root->right = findTree(A,i+1,h);
printTree(root);
cout<<endl;
}
}
Yes it is possible to construct a binary search tree from an inorder traversal. Observe that an inorder traversal of a binary search tree is always sorted. There are many possible outcomes, but one can be particularly interested in producing a tree that is as balanced as possible, so to make searches in it efficient.
Create a new tree node 'root' with the data as the maximum value found in step 1. Call buildTree for elements before the maximum element and make the built tree as left subtree of 'root'. Call buildTree for elements after the maximum element and make the built tree as right subtree of 'root'. return 'root'.
You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited.
1) Create an empty stack S. 2) Initialize current node as root 3) Push the current node to S and set current = current->left until current is NULL 4) If current is NULL and stack is not empty then a) Pop the top item from stack. b) Print the popped item, set current = popped_item->right c) Go to step 3.
This problem breaks down quite nicely into subproblems. Given an inorder traversal, after choosing a root we know that everything before that is the left subtree and everthing after is the right subtree (either is possibly empty).
So to enumerate all possible trees, we just try all possible values for the root and recursively solve for the left & right subtrees (the number of such trees grows quite quickly though!)
antonakos provided code that shows how to do this, though that solution may use more memory than desirable. That could be addressed by adding more state to the recursion so it doesn't have to save lists of the answers for the left & right and combine them at the end; instead nesting these processes, and printing each tree as it is found.
I'd write one function for constructing the trees and another for printing them.
The construction of the trees goes like this:
#include <vector>
#include <iostream>
#include <boost/foreach.hpp>
struct Tree {
int value;
Tree* left;
Tree* right;
Tree(int value, Tree* left, Tree* right) :
value(value), left(left), right(right) {}
};
typedef std::vector<Tree*> Seq;
Seq all_trees(const std::vector<int>& xs, int from, int to)
{
Seq result;
if (from >= to) result.push_back(0);
else {
for (int i = from; i < to; i++) {
const Seq left = all_trees(xs, from, i);
const Seq right = all_trees(xs, i + 1, to);
BOOST_FOREACH(Tree* tl, left) {
BOOST_FOREACH(Tree* tr, right) {
result.push_back(new Tree(xs[i], tl, tr));
}
}
}
}
return result;
}
Seq all_trees(const std::vector<int>& xs)
{
return all_trees(xs, 0, (int)xs.size());
}
Observe that for root value there are multiple trees that be constructed from the values to the left and the right of the root value. All combinations of these left and right trees are included.
Writing the pretty-printer is left as an exercise (a boring one), but we can test that the function indeed constructs the expected number of trees:
int main()
{
const std::vector<int> xs(3, 0); // 3 values gives 5 trees.
const Seq result = all_trees(xs);
std::cout << "Number of trees: " << result.size() << "\n";
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With