Pre-Order Binary Tree

[APEJMAN]

would you please help me with this question?
I know that a binary tree can be recovered from its pre-order traversal. That is, a tree built from the pre-order traversal should always be the same as the original tree. Is it true that the pre-order traversal tells the order in which the values were inserted?

[Harinezumi]

would you please help me with this question?
I know that a binary tree can be recovered from its pre-order traversal. That is, a tree built from the pre-order traversal should always be the same as the original tree. Is it true that the pre-order traversal tells the order in which the values were inserted?

No, the pre-order traversal doesn't tell you the order in which values were inserted. It tells you the values in increasing order (assuming the binary tree is sorted. However, there's no point in using a binary tree if it's not sorted - use a list then instead).
Every element in a binary tree can have two children, of which one has a smaller value, the other has a larger than the current element's (smaller and larger according to some ordering function).
The pre-order traversal means that you start out at the root of the binary tree and always go towards the smaller child, until it doesn't have a smaller child. Then you process it (e.g. print the value in it). If a processed element has a larger child, you start the same with that. If the element doesn't have any children, then you go back to the closest unprocessed element. There is a very simple recursive algorithm for this (also for the post-order traversal).
So if the tree is sorted, the tree must be the same when generated from the pre-order traversal.

[Ganon11]

The process you described is actually the in-order traversal, which says "Visit the left node first, then the current node, and finally the right node." This goes all the way down the left subtrees to find the smallest element before ever going right, and will print the tree in sorted order.

Pre-order traversal, however, says "Visit this node, then visit the left node, then visit the right node." I'm not sure, but you might be able to rebuild a tree based off of it preorder traversal with some comparisons and possibly a recursive function.

[Harinezumi]

The process you described is actually the in-order traversal, which says "Visit the left node first, then the current node, and finally the right node." This goes all the way down the left subtrees to find the smallest element before ever going right, and will print the tree in sorted order.

Pre-order traversal, however, says "Visit this node, then visit the left node, then visit the right node." I'm not sure, but you might be able to rebuild a tree based off of it preorder traversal with some comparisons and possibly a recursive function.

You're right, I mixed up the in-order and the pre-order traversal. Then it's even simpler to rebuild a binary tree using the pre-order traversal, the way Ganon11 said.

[sankar2011]

PreOder Traversal of two trees may produce the same result.