
Create a binary Tree from given Inorder and Preorder.
Last post 07142010 5:13 PM by chivalryman. 19 replies.

02162008 2:02 PM



diffuser78
 Joined on 02162008
 Posts 2

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 nonrecursive implementations.




Spectre
 Joined on 05092007
 ::1
 Posts 1,028

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.




asuffield
 Joined on 05312006
 Posts 2,137

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.




diffuser78
 Joined on 02162008
 Posts 2

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.




ZiggyFish
 Joined on 03132008
 Posts 29

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"); }




PJH
 Joined on 02142007
 Newcastle, UK
 Posts 3,923

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   


ZiggyFish
 Joined on 03132008
 Posts 29

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




Nandurius
 Joined on 05152006
 Posts 330

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 ." 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.




PJH
 Joined on 02142007
 Newcastle, UK
 Posts 3,923

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


bstorer
 Joined on 02012007
 Alexandria, VA
 Posts 4,325

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 preorder is ABC and the postorder 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 preorder. You also know it's the only child of A, because it preceeds A in the postorder. 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.




ZiggyFish
 Joined on 03132008
 Posts 29

Re: Create a binary Tree from given Inorder and Preorder.
PJH: 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).




Nandurius
 Joined on 05152006
 Posts 330

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 preorder 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 postorder 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.




ZiggyFish
 Joined on 03132008
 Posts 29

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)).




Nandurius
 Joined on 05152006
 Posts 330

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 preorder and postorder 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




ZiggyFish
 Joined on 03132008
 Posts 29

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 preorder and inorder data. So in limiting the type of tree, I've produced a better and trusted algorithm.




Nandurius
 Joined on 05152006
 Posts 330

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.




atacanc
 Joined on 12042009
 Posts 2

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; }




PSWorx
 Joined on 04282006
 Posts 1,306

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.




atacanc
 Joined on 12042009
 Posts 2

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; }




chivalryman
 Joined on 07142010
 Posts 1

Re: Create a binary Tree from given Inorder and Preorder.
Neat code. But it only works for nonduplicate 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)


