# Thread: traversing binary trees or partial trees

1. ## traversing binary trees or partial trees

Please check out the file attached as it has a binary tree on it that I don't understand.

(1) it has interior leafs and I need to follow the logic about traversing such kind of binary tree

(2) where do you start to traverse with
preorder
inorder
postorder
types of traversals???
(3) can you list the node more than once??? What is the rule here?

I came up with the following paths:
preorder : U T X U V Y W Z X Y
inorder : U T U X V W Y X Z Y
postorder : T U U V X W Y X Y Z

Are they right? Are they wrong ? Why?

2. This is surprisingly difficult to explain, so I'll try by example...
Code:
5
/ \
/   \
/     \
/       \
2         9
/ \       /
/   \     /
0     4   7
\   /   / \
1 3   6   8
For this tree,
preorder: 5 2 0 1 4 3 9 7 6 8
inorder: 0 1 2 3 4 5 6 7 8 9
postorder: 1 0 3 4 2 6 8 7 9 5

Here are the rules of the game...
First off, you have to print -all- of a node's left subtree before you can print any of the node's right subtree. No matter what kind of traversal you use.

Second off is the order in which you do it.
preorder is... (print parent) (print left subtree) (print right subtree)
inorder is... (print left subtree) (print parent) (print right subtree)
postorder is... (print left subtree) (print right subtree) (print parent)

Let's look at the preorder I have. We always start at root.
First thing I have to do it print the parent, so I print 5.
Next I print the left subtree... (2 0 1 4 3)
Then I print the right subtree... (9 7 6 8)
5 (2 0 1 4 3) (9 7 6 8)

But the catch is that the left and right subtrees have to be printed preorder as well. For example... (2 4 3 0 1) would not work because it prints the elements of the right subtree before the elements of the left subtree.

( 0 1 2 4 3) wouldn't work either because it prints the parent after printing the left subtree. It will turn out that (2 0 1 4 3) is the only preorder of the tree. All trees only have one preorder traversal, one inorder traversal, and one postorder traversal.

One important feature is that every node in the tree will be printed once, and only once.

And incidentally, your postorder answer is almost correct... that is...
(left) (right) parent
(T U U V X) (W Y X Y) Z
So that part makes sense...
(T U U) (V) X
And that part works
(no left child) (T) U U
(T) U <- This is correct version.
Okay, gotta get rid of one of those Us. Each node only needs printed once. Obviously (V) and (T) are right, since there's only 1 way to print 1 node. Now the left child...
(W) (no right node) Y X Y
(W) Y <- This is correct version.
Y is the node, so it has to come last. Before it comes the left children (W), and the right children (none) The X and Y there are clearly axtre, so take them out.

So now let's try to get back to the top and put this back together...
(T U V) X)
(W) Y
Z
(T U V X) (W Y) Z
T U V X W Y Z <- this is it

3. ok, so preorder is the only one that starts with parent and the root right off is a parent. Then goes down the left side of tree??

silly question here: How did you get the the binary tree to print in this forum without left justifying everything, elminating spaces until first character/letter or / \ was encountered??? Just drove me crazy to use this thread so I attached my txt file to show you.

4. I just wrote it up in notepad and copy and pasted it to the forum with code tags.

5. I'll try that here, inserting code with tags.

Anyways, here's another ditty about binary search trees. I missed lecture on this and I don't follow my data structure's book on searches. Can you explain this in laymen's terms?

Question: Show the search tree that would result if the following characters are inserted in the tree from left to right :

k e y b o a r d i n g

Then show the results of different types of traversals of this tree
(preorder, inorder, postorder)..

I have no idea what this tree would look like. Is there rules to how these are put in tree?

First guess is the following:

Code:
k
/    \
e       y
/  \    /  \
b    o  a     r
/  \   /  \
d    i  n    g
Whether or not this tree is created right from the characters given in the order given, I want to also understand the rules for dealing with a heap with characters.

Given this tree I have here, do I leave the letters where they are before giving the traversals OR do I sort first into heap (assuming there is a logic to the "largest" letter) and then show traversal??

Any help here would be greatly appreciated!!!

Popular pages Recent additions