Click to See Complete Forum and Search --> : Preorder == Insertion order


cthan323
February 4th, 2008, 12:24 AM
In a binary tree, will the order that values are inserted always be the same as the preorder traversal?

For example, inserting ints in this order: 6 2 1 4 3 5 7
will produce a binary tree that has the same preorder traversal.

Could someone give me an example where this is not the case?

Thanks

EDIT: Nevermind. This was a dumb question. So here is another one. Can one construct a binary tree given only one of the preorder, postorder, orinorder traversals? Or are at least two traversals needed?

CMPITG
February 4th, 2008, 01:34 AM
When you insert an item to a binary tree, it is not exactly the order of the preorder traversal. Let's say we have a tree like this:
1
/ \
/ \
/ \
3 9
/ \ / \
/ \ / \
4 2 5 6
/ / \
7 0 8
We insert items to the tree: 1 9 3 2 5 4 7 0 6 8 (this order depends on the "condition" of the binary tree).
The order of the preorder traversal: 1 3 4 7 2 0 8 9 5 6.
Binary trees can be travelled by all of those methods you mentioned, it does not depend on how we build the tree but how we need the tree ^_^