Suppose we have two array inorder and preorder containing the elements in the said format.
Using these two arrays how can i generate the binary tree??

Any help on the algorithm to be followed will be highly appreciated.

For eg:
inorder is : 2 3 4 5 6 7 8
preorder is : 5 3 2 4 7 6 8

then the Binary tree shld be
________5
________/\
_______3_7
_______/\_/\
______2_4 6_8

How can i form this binary tree??
i know the algorithm by hand but how do i implement it in C??

## All 8 Replies

> i know the algorithm by hand but how do i implement it in C??
That's basically all programming is.
If you know how to do something on paper (the hard part), writing the code for that is pretty easy.

Just a hint since I see a lot of code in here that is huge for what it is trying to do:

Build the tree recursively using the pre-order array(The in order array will cause you to have an unbalanced tree). The function to do this is 5 lines or less.

You already have an example.. try to use that to work out an algorithm

For eg:
inorder is : 2 3 4 5 6 7 8
preorder is : 5 3 2 4 7 6 8

then the Binary tree shld be
________5
________/\
_______3_7
_______/\_/\
______2_4 6_8

Hint: 5 is the root of the tree ..
5 is the first element in the pre-order array.
5 is somewhere in the middle of the in-order array .. so the elements to the left of 5 are a part of the left subtree and the elements to the right of 5 are a part of the right subtree.

resrsdghertgfsgt

hi... i have given u an code that generates a tree from a given inorder and preorder array...

``````#define NULL 0
typedef struct btree
{
int data;
struct btree *left;
struct btree *right;
}node;
node *root;
void create(int,int []);
void inorder(node *),preorder(node *);
void main()
{
int i=0,p,in;
node *list;
clrscr();
printf("enter the preorder\n");
while(1)            //getting array for preorder elements
{
scanf("%d",&p[i]);
i++;
if(p[i-1]==-99)
break;
}
printf("enter the inorder\n");
i=0;
while(1)             //getting array for inorder elements
{
scanf("%d",&in[i]);
i++;
if(in[i-1]==-99)
break;
}
printf("\nthe given inorder is\n");
for(i=0;in[i]!=-99;i++)
printf("%5d",in[i]);
printf("\nthe giver preorder is\n");
for(i=0;p[i]!=-99;i++)
printf("%5d",p[i]);
root=(node*)malloc(sizeof(node));
root->data=p; //by default first elemnt of tree is p
root->right=root->left=NULL;
for(i=1;p[i]!=-99;i++)
create(p[i],in);//creating tree for each element of preorder using inorder array
printf("\n\n\nINORDER TRAVERSAL OF THE TREE\n");
inorder(root);
printf("\n\n\nPREORDER TRAVERSAL OF THE TREE\n");
preorder(root);
getch();
}

void create(int key,int a[])
{
node *i=root,*j;
while(1)
{
if(find(i->data,a,key))//finding the position of p[i](here key)to be inserted in tree
{
if(i->left==NULL)
{
i->left=(node*)malloc(sizeof(node));
i=i->left;
i->data=key;
i->left=i->right=NULL;
break;
}
else
i=i->left;
}
else
{
if(i->right==NULL)
{
i->right=(node*)malloc(sizeof(node));
i=i->right;
i->data=key;
i->left=i->right=NULL;
break;
}
else
i=i->right;
}

}
}
int find(int t,int a[],int key)
{
int i,j;
for(i=0;a[i]!=-99;i++)
if(a[i]==t)
break;
for(j=0;j<i;j++)
if(a[j]==key)
return 1;
return 0;
}

void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%6d",root->data);
inorder(root->right);
}
}
void preorder(node *root)
{
if(root!=NULL)
{
printf("%6d",root->data);
preorder(root->left);
preorder(root->right);
}
}``````

try ur problem wit this solution.
Tell me whether it is useful for U :-)

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct Tree
{
char chr;
Tree *left, *right;
};

queue<Tree *> q;
char PreOrder;
char InOrder;
bool flag;
int Pid;
int PLen, ILen;

Tree *ReBuild(int a, int b)
{
int id;
int k;
Tree *node;

Pid ++;
node = new Tree;
node->chr = PreOrder[Pid];

for (int i = a; i <= b; i ++)                 //对于前序遍历序列的元素，在中序遍历序列中寻找它的位置
if (InOrder[i] == PreOrder[Pid])
id = i;
flag[id] = true;

for (k = id - 1; k >= a; k --)              //构造该根的左子树
if (flag[k] == true)
break;

if (k == id - 1)                                 //注意边界地方的讨论
node->left = NULL;
else if (k == a - 1)
node->left = ReBuild(a, id - 1);
else
node->left = ReBuild(k, id - 1);

for (k = id + 1; k <= b; k ++)           //构造该根的右子树
if (flag[k] == true)
break;

if (k == id + 1)                                //注意边界地方的讨论
node->right = NULL;
else if (k == b + 1)
node->right = ReBuild(id + 1, b);
else
node->right = ReBuild(id + 1, k);

return node;
}

void visit()
{
Tree *temp;

while (!q.empty())
{
temp = q.front();

printf("%c", temp->chr);

if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);

q.pop();
}

printf("\n");
}

void destroy(Tree *node)
{
if (node == NULL)
return ;

if (node->left)
destroy(node->left);
if (node->right)
destroy(node->right);

delete node;
}

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int T;
Tree *root;
scanf("%d", &T);

while (T --)
{
memset(flag, false, sizeof(flag));
scanf("%s%s", PreOrder, InOrder);

Pid = -1;
root = ReBuild(0, strlen(InOrder) - 1);

q.push(root);
visit();                                   //广度优先遍历

destroy(root);
}

return 0;
}``````

Hey thanks for providing code. . .
I'll check it and will get back to you soon.

here i have another code without recursion:

``````template <typename Comparable>
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(){
left = right = NULL;
}
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt ) { }
};
void binTree( BinaryNode<char>*&root, string s, string t)
//Build a binary tree root so that its preorder traversal is s and its inorder traversal is t.
//scan preorder from left to right using inorder to seperate left and right subtrees.
{
root = new BinaryNode<char>(s,NULL,NULL);
/*int p[s.length()];
for(int i = 0 ; i < s.length();i++)
for(int j = 0 ; j < t.length(); j++)
if(s[i] == t[j])
p[i] = j;*/
BinaryNode<char>* parent;
BinaryNode<char>* current;

for(unsigned int i = 1; i < s.length(); i++)
{
current = root;
BinaryNode<char>* target = new BinaryNode<char>(s[i],NULL,NULL);
while(current){
if(t.find(target->element) < t.find(current->element) )
{
parent = current;
current = current->left;
}
else if(t.find(target->element) > t.find(current->element)){
parent = current;
current = current->right;
}
else;
}
if(t.find(target->element) < t.find(parent->element))
parent->left = target;
else
parent->right = target;
}
}

template<typename Comparable>
void levelTraversal(BinaryNode<Comparable>* sub_root,void(*visit)(Comparable & x)){
queue<BinaryNode<Comparable>*> q ;

//must justify sub_root is not empty, otherwise there's an exception
if(sub_root != NULL){
q.push(sub_root);

while(!q.empty()){
if(q.front()->left != NULL)
q.push(q.front()->left);
if(q.front()->right != NULL)
q.push(q.front()->right);
(*visit)(q.front()->element);
q.pop();
}
}
}

template<typename Comparable>
void printTree( BinaryNode<Comparable> *t )
{
if( t != NULL )
{
printTree( t->left);
cout << t->element << endl;
printTree( t->right);
}
}

template<typename T>
void print(T & x){
cout << x << " ";
}

int main(){

string pre = "gdhbeiafjc";
string in = "abdgheicfj";
BinaryNode<char>* root = new BinaryNode<char>();
binTree(root,pre,in);
printTree(root);
levelTraversal(root,print<char>);
}``````

i think this one is much more understandable and it is my original implementation. string_name.find(char) returns the int postion of the char which simplify the code a lot..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.