Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

constructing a binary tree from its inorder and preorder traversals

Prakash_RadhaPrakash_Radha Posts: 14Member
Given: Two arrays representing the inorder and preorder traversals of a binary tree.....

ex: Inorder: 2 9 3 5 4 1 7 6 8
Preorder:1 2 3 9 4 5 6 7 8


I want to construct the binary tree from this two arrays.....

Any suggestions would be welcome.....

thanks,
prakash.

Comments

  • HK_MP5KPDWHK_MP5KPDW Posts: 770Member ✭✭✭
    : Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
    :
    : ex: Inorder: 2 9 3 5 4 1 7 6 8
    : Preorder:1 2 3 9 4 5 6 7 8
    :
    :
    : I want to construct the binary tree from this two arrays.....
    :
    : Any suggestions would be welcome.....
    :
    : thanks,
    : prakash.
    :
    [blue]As I understand it, an inorder traversal would only give you the elements in their sorted order regardless of the order they were initially stored in. Therefore it is impossible to determine the original shape of the tree given an inorder sequence of values.

    As I have found in the past, looking at the preorder output of the contents of a binary tree is an easy way to figure out the original shape. Given your values, the tree must look like this:
    [code]
    1

    2

    3

    9
    /
    4

    5

    6

    7

    8
    [/code]This isn't much of a binary tree is it? Looks just like a sequential linked list at this point. This is in serious need of balancing.[/blue]
  • Prakash_RadhaPrakash_Radha Posts: 14Member
    : : Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
    : :
    : : ex: Inorder: 2 9 3 5 4 1 7 6 8
    : : Preorder:1 2 3 9 4 5 6 7 8
    : :
    : :
    : : I want to construct the binary tree from this two arrays.....
    : :
    : : Any suggestions would be welcome.....
    : :
    : : thanks,
    : : prakash.
    : :
    : [blue]As I understand it, an inorder traversal would only give you the elements in their sorted order regardless of the order they were initially stored in. Therefore it is impossible to determine the original shape of the tree given an inorder sequence of values.
    :
    : As I have found in the past, looking at the preorder output of the contents of a binary tree is an easy way to figure out the original shape. Given your values, the tree must look like this:
    : [code]
    : 1
    :
    : 2
    :
    : 3
    :
    : 9
    : /
    : 4
    :
    : 5
    :
    : 6
    :
    : 7
    :
    : 8
    : [/code]This isn't much of a binary tree is it? Looks just like a sequential linked list at this point. This is in serious need of balancing.[/blue]
    :



    hi, the thing is u have to use the information in both the arrays to determine the tree.... i've come up with a solution.....
    The first element in the preorder array will be the root. Now traverse the inorder array till u find that inorder array element. Now all those elements in the preorder array which are to the left of the element found will come in the left subtree and all those elements to the right will come in the right subtree....

    Recursively do the same till u exhaust all the elements in the array.
    Thanks for ur suggestion.bye.

    prakash.
  • CppKidCppKid Posts: 4Member
    : Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
    :
    : ex: Inorder: 2 9 3 5 4 1 7 6 8
    : Preorder:1 2 3 9 4 5 6 7 8
    :
    :
    : I want to construct the binary tree from this two arrays.....
    :
    : Any suggestions would be welcome.....
    :
    : thanks,
    : prakash.
    :

    Hi,

    Can you share the C++ code, if you have? I need this for my assignment.
  • bijan1384bijan1384 Posts: 1Member
    please if you find pesude code of this problem set in the messageboar

  • HK_MP5KPDWHK_MP5KPDW Posts: 770Member ✭✭✭
    : please if you find pesude code of this problem set in the messageboar
    :

    You mean pseudocode? Generally you should not bump threads that are more than perhaps a week or so old. What you should do is make a new post explaining your problem and perhaps with a link to this old post as a reference. That said, a C++ version with the important bit in pseudocode is as follows:

    [code]
    struct node
    {
    int data;
    node* lptr;
    node* rptr;
    node(int val) : lptr(0), rptr(0), data(val)
    {
    }
    };

    node* buildtree(int* inorder,int* preorder,int left,int right,int& current)
    {
    1. Test if left is equal to right and return NULL if it is.
    2. Create a new temporary node with value of preorder[current].
    3. Return this new temporary node if left+1 is equal to right.
    4. Search starting from inorder+left up to inorder+right and get
    an int pointer to the element that has the same value as
    preorder[current].
    5. Find the distance from the start of the inorder array to this
    pointer, call it position.
    6. If position is greater than left then...
    6a. Increment current
    6b. Set the lptr of the temporary node equal to the return
    value of buildtree(inorder,preorder,left,position,current)
    7. If position+1 is less than right then...
    7a. Increment current
    7b. Set the rptr of the temporary node equal to the return
    value of buildtree(inorder,preorder,position+1,right,current)
    8. Return the temporary node
    }

    int main()
    {
    int preorder[] = { 6, 15, 1, 23, 9, -9, 22 };
    int inorder[] = { 23, 1, 15, 9, 6, 22, -19 };
    int count = 0;
    node* root = buildtree(inorder,preorder,0,7,count);
    // root now points to the root of the binary-search tree
    // built from the two arrays.
    }
    [/code]
Sign In or Register to comment.