The Daily WTF: Curious Perversions in Information Technology
Welcome to TDWTF Forums Sign in | Join | Help
in Search

Create a binary Tree from given Inorder and Preorder.

Last post 07-14-2010 5:13 PM by chivalryman. 19 replies.
Page 1 of 1 (20 items)
Sort Posts: Previous Next
  • 02-16-2008 2:02 PM

    Create a binary Tree from given Inorder and Preorder.

     The prototype is

    btreenode* create_binary_tree(char *inorder, char *preorder, int length)

    where length is the length of the string when contents of binary tree are written in sequential fashion.


    btreenode is as follows

    typedef struct btreenode{
         struct btreenore *left;
         char data;
         struct btreenode *right;
    }

     

    Compare your recursive and non-recursive implementations.  

  • 02-16-2008 4:43 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    Wow, wow, I'm so excited at the thought of doing somebody else's homework; I, I think, I'll just explode right now!
    ╩юфют√ь ёЄЁрэшЎрь яюЁр эр яхэёш■.

    #TDWTF @ SlashNET was merged into #codelove @ the same network. You're still welcome to drop by. I guess.
  • 02-16-2008 9:19 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    I am sorely tempted to produce the most convoluted and subtly but fundamentally wrong solution that I can think of.

  • 02-16-2008 11:05 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

     I thought its a coder challege and you guys need some problem for food. 

     

    Its not my homework dear...trust me on that.  

  • 03-13-2008 7:15 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    By it's definition preorder is the order inwhich they were added, so knowing that is just a matter of adding each node sequentially.

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

    typedef struct tag_btreenode{
         struct tag_btreenode *left;
         char data;
         struct tag_btreenode *right;
    } btreenode;


    void tree_insert(btreenode* root, char data){
        btreenode* curNode;
        curNode = root;

        while(1){
            if (data > curNode->data){
                if (curNode->right == NULL){
                    curNode = curNode->right = malloc(sizeof(btreenode *));
                    curNode->data = data;
                    curNode->left = NULL;
                    curNode->right = NULL;
                    return;
                }else
                    curNode = curNode->right;
            }else{
                if (curNode->left == NULL){
                    curNode = curNode->left = malloc(sizeof(btreenode *));
                    curNode->data = data;
                    curNode->left = NULL;
                    curNode->right = NULL;
                    return;
                } else
                    curNode = curNode->left;
            }
        }
    }

    btreenode* create_binary_tree(char *inorder, char *preorder, int length){
        int i;
        btreenode *root = malloc(sizeof(btreenode *));
        root->data = *preorder;
        root->left = NULL;
        root->right = NULL;
        for(i=0;i<length;i++){
            tree_insert(root, preorder[i]);
        }
        return root;
    }


    void tree_traverse(btreenode* root){
        if (root == NULL)
            return;   
        tree_traverse(root->left);
          printf("%c", root->data);
        tree_traverse(root->right);

       
    }
    int main(){
        printf("New tree is: ");
        tree_traverse(create_binary_tree("ABCDEFGHI", "FBADCEGIH", 9));
        printf("\n");
    }



  • 03-14-2008 5:27 AM In reply to

    • PJH
    • Top 10 Contributor
    • Joined on 02-14-2007
    • Newcastle, UK
    • Posts 3,917

    Re: Create a binary Tree from given Inorder and Preorder.

    ZiggyFish:
    By it's definition preorder is the order inwhich they were added
    [Citation required]

    "Because you watched 'The Very Hungry Caterpillar,' we recommend 'The Human Centipede.'"
    --
    UED - Countryside: To kill Piers Morgan
  • Parp!
  • 03-14-2008 6:41 AM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    Is this a stab at me? Anyway here is your citation. 

    http://www.brpreiss.com/books/opus4/html/page258.html 



  • 03-14-2008 7:33 AM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    ZiggyFish:

    Is this a stab at me? Anyway here is your citation. 

    http://www.brpreiss.com/books/opus4/html/page258.html 

     

    I think what he was trying to say is that it's not that simple and that you should look it up. I think you're misreading the page you linked. It only says that " Notice that the preorder traversal visits the nodes of the tree in precisely the same order in which they are written in Equation gif." It does not say that it's the order in which the items were inserted.

     In your example, you're inserting the nodes "ABCDEFGHI", which are in ascending order. Your insertion algorihtm would always insert the next element to the first available "right" branch. You end up with a tree that's 9 levels deep and essentially a linear list, with left == null and right == next.

    That's just one of the many trees that the preorder traversal "ABCDEFGHI" can describe though. Take this tree for example:

    The preorder traversal is also ABCDEFGHI, but since this binary tree is not a sorted tree you don't recreate it properly. This is why you need the post order traversal. Using both, you should be able to determine if B is on the left or right side of the root.  I'm not sure if it's free of ambiguities though. If you only take the nodes {A, B, C} from the above tree, the preorder traversal is "ABC" and so is the post order traversal. If you "flip the tree vertically", (D becomes B, E becomes C) then the pre and post order traversals are the same. That means that for some types of trees (unbalanced trees that have gaps in the branches) it's impossible to recreate the original tree without further information.

  • 03-14-2008 7:46 AM In reply to

    • PJH
    • Top 10 Contributor
    • Joined on 02-14-2007
    • Newcastle, UK
    • Posts 3,917

    Re: Create a binary Tree from given Inorder and Preorder.

     

    ZiggyFish:
    http://www.brpreiss.com/books/opus4/html/page258.html 
    Then you have clearly misread it. Your cite does not say that pre-order is the
    order in which they were added,
    It says: 

    in precisely the same order in which they are written in Equation <link>

    Specifically (using their example) if the nodes were added in the order

    E F G H I A B C D

    That is not the order a pre-order traversal will return them in. You indicated (mistakenly or not) otherwise. 

    "Because you watched 'The Very Hungry Caterpillar,' we recommend 'The Human Centipede.'"
    --
    UED - Countryside: To kill Piers Morgan
  • Parp!
  • 03-14-2008 12:09 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    Nandurius:
    That's just one of the many trees that the preorder traversal "ABCDEFGHI" can describe though. Take this tree for example:

    The preorder traversal is also ABCDEFGHI, but since this binary tree is not a sorted tree you don't recreate it properly. This is why you need the post order traversal. Using both, you should be able to determine if B is on the left or right side of the root.  I'm not sure if it's free of ambiguities though. If you only take the nodes {A, B, C} from the above tree, the preorder traversal is "ABC" and so is the post order traversal.

    If our tree is only A, B, and C, the pre-order is ABC and the post-order is CBA.

    If you "flip the tree vertically", (D becomes B, E becomes C) then the pre and post order traversals are the same. That means that for some types of trees (unbalanced trees that have gaps in the branches) it's impossible to recreate the original tree without further information.
     

    You definitely need more information.  Consider your {A,B,C} example.  You can be certain that B is a child of A, because it immediately follows A in the pre-order.  You also know it's the only child of A, because it preceeds A in the post-order.  But you can't be certain of whether it's the right or left child.  The same is true of C.  You can solve this problem for particular subsets of binary trees, for example, if you have the rule that if a node has one child node, it must be the left one.


    Now I am become Death, the destroyer of worlds.
  • 03-14-2008 7:59 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    PJH:

    E F G H I A B C D

     

     

    The idea still is the same weather of not there in the same order,your example would produce the following preorder:

    E A B C D F G H I

    Using the same logic as you would normally do, E becomes the root node(because at this point there is no nodes in the tree), then A (as it's less then E, goes to the left),  B to the right of A (because B is less then E but greater than A), etc.

     

    As another example from the link (using the following values as the letters (because obvoisly this isn't a btree)):

     

    A = 12

    B =  6

    C = 9

    D = 20

    E = 16

    F = 15

    G = 17

    H = 27

    I = 26

    The preoder becomes 

    12 6 9 20 16 15 17  27 26

    Using my logic:

    12 becomes the root node (because we don't have any nodes in the tree), 6 is less then 12 so it goes to the left, 9 is less then 12 but greater than 6 so it goes the the right of 6, 20 is greater than 12 so it goes to the right of 12. 16 is greater than 12 but less than 20 so it goes to the left of 20, 15 is greater than 12 but less then 20 and 16, so it goes to the left of 16. 17 is greater than 12 but less then 20 but greater than 16 so it goes to the right of 16. 27 is greater than 12 and 20, so it goes to the right of 27, 26 is greater than 12 and 20, but less than 27. 

    So as such the problem is as simple as adding the nodes to an empty tree in an interation (If you can find a tree where this doesn't hold true then tell me).



  • 03-14-2008 8:42 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

     Again, you are mistakenly assuming that you're dealing with sorted trees. I think you're right that, given a pre-order tree traversal AND the insertion constraints that 'lesser' values are added to the left branch, 'greater' values to the right branch, you can recreate the original tree.

     However, sorted trees are only a subset of binary trees and the original question was *NOT* restricted to sorted trees. Therefore you absolutely have to take into account the post-order traversal since you can NOT assume that the nodes follow your insertion rules.

     

    ZiggyFish:
    (If you can find a tree where this doesn't hold true then tell me).
     

    Any tree that isn't sorted. 

  • 03-14-2008 9:19 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    We than the solution to this problem is not posible (i.e  preoder of 1 1 1 1 1 1 1 1, inorder of 1 1 1 1 1 1 1 1 (and the postorder of 1 1 1 1 1 1 1 1)).



  • 03-14-2008 9:38 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    ZiggyFish:

    We than the solution to this problem is not posible

     

    It's not always possible. We already pointed that out about 3 posts above. It is possible for many trees though, and using both the pre-order and post-order traversal log it's possible to recreate them.

    It's a pretty common assignment when teaching binary trees. See this page for example for more examples, some test cases and a solution in pascal.

    http://www.cise.ufl.edu/~acm/HSPC/1996/questions/tree.shtml     

  • 03-14-2008 10:14 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    But the solution can never be trusted(given the right input) to produce the correct tree (as mine only works on trees that are binary search trees, it will always work) and as such is not a solution. It like saying the tree must have one solution (or you won't get a result), where as mine would work on any binary search tree (and as such can be trusted with any data). Also my solution produces the correct tree for more pre-order and inorder data.

    So in limiting the type of tree, I've produced a better and trusted algorithm.



  • 03-15-2008 5:25 AM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    ZiggyFish:
    So in limiting the type of tree, I've produced a better and trusted algorithm.

    That's jolly good, but it doesn't have anything to do with this thread any more. I can produce a better, faster and just as reliable algorithm by limiting the tree to a single node.

     

    String treeFromPreAndPost(String pre, String post)
    {
         if( pre != null && post != null && pre.equals(post) && pre.length() == 1)
         {
              return pre;
         }
         return "invalid input";
    }
     But just as your algorithm, this one doesn't do what the challenge required.
  • 12-03-2009 7:35 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    If the elements can repeat the inorder might be equal to preorder therefore there can not be solution. So the elements must be unique for this question to be solved.

    Here is a recursive solution:

    struct TreeNode
    {
      struct TreeNode* left;
      struct TreeNode* right;
      int  elem;
    };

    TreeNode* BinaryTreeFromOrderings(int* inorder, int* preorder, int length)
    {
      if(length == 0)
        {
          return NULL;
        }
      //We have root then;
      TreeNode* node = new TreeNode;
      node->elem = *inorder;
      int rootIndex = 0;
      for(;rootIndex < length; rootIndex++)
        {
          if(inorder[rootIndex] == *inorder)
            {
               break;
            }
        }
      //Left
      node->left = BinaryTreeFromOrderings(inorder+1, preorder, rootIndex);
      //Right
      node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
      return node;
    }

  • 12-04-2009 2:29 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

     While I'm sure that code took some effort and this is usually no way to greet newcomers, I believe this still calls for the

    In this reflect, welcome to the forums.

  • 12-07-2009 7:45 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    Do you have another card for smoking weed and doing a code posting? :)

    There are several obvious mistakes in the code I have posted... Here is the working one:

    TreeNode* BinaryTreeFromOrderings(int* inorder, int* preorder, int length)
    {
      if(length == 0)
        {
          return NULL;
        }
      //We have root then;
      TreeNode* node = new TreeNode;
      node->elem = *preorder;
      int rootIndex = 0;
      for(;rootIndex < length; rootIndex++)
        {
          if(inorder[rootIndex] == *preorder)
     {
       break;
     }
        }
      //Left
      node->left = BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
      //Right
      node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
      return node;
    }

  • 07-14-2010 5:13 PM In reply to

    Re: Create a binary Tree from given Inorder and Preorder.

    Neat code. But it only works for non-duplicate keys. For the following example: inorder: A B C A E F G H I preorder: E A B C A F G H I The code will be broken

Page 1 of 1 (20 items)
Powered by Community Server (Non-Commercial Edition), by Telligent Systems