Problem

Given a preorder traversal of a binary search tree. Create the tree and print the tree. (Assume all the nodes are unique)

Description

This problem covers three concepts.

• Insertion of a node into a BST
• Understanding preorder traversal
• Printing a tree

Printing a tree

Printing trees in top to bottom manner is not ideal with how we use our screens.
Mostly we have scrollable pages in vertical direction, hence we have more space in vertical direction. Horizontal direction is just limited to the screen width.
But as we know the height of the tree is h ~ log(n) while width of the tree w ~ n/2.
As the width increases exponentially faster than the height of the tree, it would be ideal to print trees from left to right. That is column wise. In the first column just the root node, in second column the nodes at level 1, in third column the nodes at level 2 and so on.
For a more general tree (with more than 2 children) we can just print the parent node at top and then the whole subtree below it, and next subtree below that one and so on. But for Binary trees we can do better. We can print the parent node in the middle of two subtrees. This gives a nice visual feel of the whole tree.
One more advantage of printing BST in such a manner is that, all the nodes are printed in sorted manner (descending) from top to bottom. Each row will have just a single node and the column represent the depth of node.

Preorder Traversal

In a preorder traversal we traverse the root node, then left subtree in recursive manner, and then right subtree.

Binary Search Tree

Binary search tree is a binary tree which follows the invariant that for each node the max value in the left subtree of the node is less than the node value, and the min value of the right subtree is greater than the node value. Equality case can be decided to place at any one side.

Explaination

From the structure of a BST and the way preorder traversal is done, it is not difficult to see that we can start inserting the nodes in the order of preorder traversal and it will create a BST that will give out the same preorder traversal. (Given that all entries of preorder traversal are unique)

Bonus

For the testing of the code and sample run, we have created a method that gives the preorder traversal of a binary tree. It uses stack concepts for the implementation. This can also be done recursively in very few lines. But a recursive solution takes heap space.

Code

https://ideone.com/2RJPNA

Code

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct Node {
	int x;
	Node *l;
	Node *r;
	Node(int value=0, Node* left=NULL, Node* right=NULL) : x(value), l(left), r(right) {}
};

void print_binary_tree(Node* node, int depth=0){
	if(!node)	return;
	print_binary_tree(node->r, depth+1);
	string str = "";
	for(int i=0; i<depth; i++)
		cout<<"|\t";
	cout<<node->x<<endl;
	print_binary_tree(node->l, depth+1);
	return;
}
void insert(Node* &root, Node* node){
    if(!root)   root = node;
    else insert(node->x<root->x?root->l:root->r, node);
}
Node* preorderd_to_bst(const vector<int> &v){
	Node* root = NULL;
	for(int x: v)
        insert(root,new Node(x));
    return root;
}
vector<int> bst_to_preorder(Node* root){
	stack<Node*> h;
	Node* node;
	h.push(root);
	vector<int> v;
	while(!h.empty()){
		node = h.top();
		h.pop();
		if(!node)	continue;
		v.push_back(node->x);
		h.push(node->r);
		h.push(node->l);
	}
	return v;
}
void random_run(int n = 100){
	Node* root = NULL;
	while(n--)
        insert(root,new Node(rand()%1000));
	cout<<"Original Tree"<<endl;
	print_binary_tree(root);
	cout<<endl;
	vector<int> preorder = bst_to_preorder(root);
	cout<<"Preorder Traversal"<<endl;
	for(int x: preorder)
		cout<<x<<' ';
	cout<<endl<<endl;
	root = preorderd_to_bst(preorder);
	cout<<"Answer Tree"<<endl;
	print_binary_tree(root);
	cout<<endl;
}
int main() {
	int t,n,x;
	Node* root;
	vector<int> v;
	cin>>t;
	while(t--){
		cin>>n;
		v.clear();
		while(n--&&cin>>x)	v.push_back(x);
		root = preorderd_to_bst(v);
		print_binary_tree(root);
		cout<<endl;
	}
	random_run();
	return 0;
}

Ideone it!