[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
Solved

# Help required in a traversal program

Posted on 2006-05-20
Medium Priority
222 Views
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.

0
Question by:swtirs
• 2

LVL 45

Accepted Solution

sunnycoder earned 1500 total points
ID: 16725371
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

LVL 16

Expert Comment

ID: 16725375
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

LVL 45

Expert Comment

ID: 16725383
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month20 days, left to enroll