Help required in a traversal program

Posted on 2006-05-20
Last Modified: 2010-04-15
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.

Question by:swtirs
    LVL 45

    Accepted Solution

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

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

    LVL 16

    Expert Comment

    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?

    LVL 45

    Expert Comment

    Hi Paul,


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


    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    This tutorial is posted by Aaron Wojnowski, administrator at  To view more iPhone tutorials, visit This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
    This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
    The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

    729 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    19 Experts available now in Live!

    Get 1:1 Help Now