Generating a Binary tree from inorder and preorder

Question

basukinjal 0 Newbie Poster

17 Years Ago

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??

algorithm-pseudocode c

8 Contributors
8 Replies
542 Views
2 Years Discussion Span
Latest Post 15 Years Ago Latest Post by xinhedanti

Dani AI

Generated 10 Months Ago

Short answer: use preorder to pick the root and split inorder into left/right ranges, but avoid scanning the inorder array repeatedly. As and note, the root is preorder[0] and recursion is natural; to make the C implementation scale, precompute a fast value→index lookup (here I use a small portable trick with qsort+bsearch). That drops repeated O(n) scans and makes construction O(n log n) (or O(n) if you replace the lookup with a hash table).

Algorithm sketch: build an array of (value,index) from the inorder array and sort it. Keep an integer preIdx that advances through preorder. Recursive build(inL,inR) takes preorder[preIdx++] as the root, looks up its index in inorder via bsearch, then builds left with [inL, idx-1] and right with [idx+1, inR]. Base case is inL > inR. This assumes unique values and that preorder/inorder contain the same elements — check bsearch results to detect bad input.

A compact, portable C implementation (original) — drop this into your project and call buildTree(pre, in, n):

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int val; struct Node *left,*right; } Node;
typedef struct Pair { int val; int idx; } Pair;

int cmpPair(const void *a, const void *b){
    int va = ((Pair*)a)->val, vb = ((Pair*)b)->val;
    return (va < vb) ? -1 : (va > vb);
}

Node* newNode(int v){ Node* p = malloc(sizeof *p); p->val=v; p->left=p->right=NULL; return p; }

Node* build(int pre[], int *preIdx, int inL, int inR, Pair pairs[], int n){
    if(inL>inR) return NULL;
    int rootVal = pre[(*preIdx)++];
    Pair key = { rootVal, 0 };
    Pair *found = bsearch(&key, pairs, n, sizeof(Pair), cmpPair);
    if(!found) return NULL; /* invalid input */
    int idx = found->idx;
    Node *r = newNode(rootVal);
    r->left  = build(pre, preIdx, inL, idx-1, pairs, n);
    r->right = build(pre, preIdx, idx+1, inR, pairs, n);
    return r;
}

Node* buildTree(int pre[], int in[], int n){
    Pair *pairs = malloc(sizeof(Pair)*n);
    for(int i=0;i<n;i++){ pairs[i].val=in[i]; pairs[i].idx=i; }
    qsort(pairs, n, sizeof(Pair), cmpPair);
    int preIdx = 0;
    Node *root = build(pre, &preIdx, 0, n-1, pairs, n);
    free(pairs);
    return root;
}

Notes and pitfalls: handle duplicates specially (store lists of indices), validate that preorder/inorder are same multiset, free the allocated nodes after use, and beware deep recursion for skewed trees (use an iterative rebuild or increase stack). The version by works but repeatedly searches inorder; this approach trades a small preprocessing step for much better performance on larger inputs.

All 8 Replies

Salem 6,009 Posting Sage

17 Years Ago

> 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.

Post your idea and your attempt at the code.

rpiper138 46 Newbie Poster

17 Years Ago

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.

Reply to this topic

Be a part of the DaniWeb community

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

stilllearning 148 Posting Whiz · Answer 1 · 2008-09-30T02:56:22+00:00

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.

aman161089 0 Newbie Poster · Answer 2 · 2010-08-24T20:48:08+00:00

aman161089 0 Newbie Poster

16 Years Ago

resrsdghertgfsgt

srinivasan106 0 Newbie Poster · Answer 3 · 2010-08-25T16:24:02+00:00

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[30],in[30];
	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[0]; //by default first elemnt of tree is p[0]
	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 :-)

xinhedanti 0 Newbie Poster · Answer 4 · 2011-04-13T20:26:06+00:00

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

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

queue<Tree *> q;
char PreOrder[500];
char InOrder[500];
bool flag[500];
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;  
}

yashsaxena -1 Light Poster · Answer 5 · 2011-04-14T18:03:36+00:00

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

xinhedanti 0 Newbie Poster · Answer 6 · 2011-04-14T18:24:56+00:00

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[0],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..

Generating a Binary tree from inorder and preorder

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers