• C

Help required in a traversal program

I need to write a program in ‘C’ language that could accept inorderr and pre-order traversal outputs of a Binary Tree as input and prints the corresponding Binary tree.

swtirsAsked:
Who is Participating?
 
sunnycoderConnect With a Mentor Commented:
What is the help required?

This sounds very much like homework and Membership Agreements fobids posting solutions to homework questions ... If you have some specific query, post here and we will be glad to help but we cant solve the entire problem for you ...

Here are some hints to get you started::

Assume
inorder = g d h b e i a f j c
preorder = a b d g h e i c f j
                ^
Scan the preorder left to right using the inorder to separate left and right subtrees.
a is the root of the tree; gdhbei are in the left subtree; fjc are in the right subtree.

preorder = a b d g h e i c f j
                 ^^
b is the next root; gdh are in the left subtree; ei are in the right subtree.

preorder = a b d g h e i c f j
                 ^^^
d is the next root; g is in the left subtree; h is in the right subtree.

The basic idea hence is ... The first node in preorder traversal is the root ... The nodes on the left of this node in inorder traversal form its left subtree and nodes to the right in inorder traversal form the right sub-tree ...

This algorithm can be recursively applied to each subtree!!

Cheers!
sunnycoder
0
 
PaulCaswellCommented:
Hi swtirs,

1. Could you clarify 'inorder' and 'pre-order'. I think I know what you mean but just to clarify.

2. What form do you want the output in?

Paul
0
 
sunnycoderCommented:
Hi Paul,

1.
http://en.wikipedia.org/wiki/Tree_search_algorithm

2.
Beware, this is common problem in data structures/ advanced data structures course

Cheers!
sunnycoder
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.