inserting characters into a binary tree

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

I get -

Code:

	      k
	     /   \
	    e      y
           /  \   / \
	  b    i  o
	 / \   / / \
	a   d  g n  r

For each entry you start at the root. If it's less than the node insert to the left, if it's greater insert to the right and continue until you find a empty child. Everything to the left of 'k' should be less than it and to the right greater, and so on throughout the tree.

If you're implementing a binary search tree then you don't need a 'heap' and can traverse the tree as it is.

Zen,

I am not following your logic of
< goes on left
> goes on right

Code:

                      k
                    /   \
                  e      y
                 /  \   /  \
                b                                  <------ I get this to this point

why would the "o" then go to the right of 'parent y' instead of
'parent e' if e is the same node we are on after placement of
'b'???

Why wouldn't each letter be moved to the next child of same node if it fits the rule, else go to node on same level and fit in child of that node that it fits, then if that level is full and letter coming in doesn't fit rule for any node on that level go to the next level of nodes until all are placed?? Is there a rule I am missing/forgeting about filling in children and leaving too many "leaves" open??

Code:

                         k 
                       /    \
                      /       \
                    e           y
                  /    \        /  \
                 /      \      /     \
                b       o     a    
               /   \    / \    / \
              /     \  /   \  /   \
                    r  d      i
                  / \  /\
                 /   \/  \
                n        g

why would the "o" then go to the right of 'parent y' instead of
'parent e' if e is the same node we are on after placement of
'b'???

It'd go on the left of 'y' as it's less than it.

Starting from the root 'o' is greater than 'k' so it'd go to the right. 'y' exists to the right of 'k' so repeat the comparison. 'o' is less than 'y' so it goes to the left. There's no existing node there so that's where it's inserted. For a plain binary search tree, after each placement you return to the root to find the insertion point for the next node and don't continue from the last place where a node was inserted.

I understand now. Thanks.