Traversing and inserting into a weird binary tree [SOLVED]

Question

Ok, I ran into this tree question which LOOKED simple, but started driving me nuts.

The tree given is LIKE a binary search tree, but with one difference:

1. For a Node, leftNode.value < value <= rightNode.value. However, (by their omission of any further info, and by their example below) this ONLY applies to the immediate children, not the nodes beneath each child. So it's possible to have a value somewhere in the left subtree that is >= the current node's value.

This is NOT a self-balancing tree; the existing tree structure will not be changed on an insert, aside from adding the new value in a new leaf node. No switches or shifts of values or nodes allowed.

Also given was an example of the tree structure after test values were inserted:

If we insert 8, 5, 9, 3, 3, 2, 12, 4, 10:


   8


   8
  5  


   8
  5 9


   8
  5 9
 3


   8
  5 9
 3
  3


   8
  5 9
 3   
2 3


   8
  5 9
 3   12
2 3


   8
  5 9
 3   12
2 3
   4


    8
  5   9
 3  10 12
2 3
   4

I assumed the 10 was the right child of 5, since the given constraint prevents it from being the left child of 9.

My requirements, given the rule above for nodes and the example of expected tree structure and behavior for given input: write a traversal and insertion algorithm for this tree.

Since this isn't a real BST and we're not allowed to alter the tree, I couldn't think of any clever way to perform traversal, other than using another data-structure to get this in order.

I've got an insertion algorithm which might work, but since it would have to allow back ups to the parent node and exploration of the other path (in both cases where it starts traveling down the left or the right), it would be a really funky looking algorithm.

This question was placed alongside normal, basic programming questions, so it seemed a little out of place. So...any insights here? Or am I overlooking something obvious?

EDIT: Problem solved. It WAS a typo introduced by the test-giver. This was meant to be a BST, but the "10" in the example was placed in the wrong position; it should have been the left child of "12".

Answer 1

Te examples makes sense until the 10 appears. Basic assumption: It's a typo. But it can't (and doesn't look to) be a child of 5. It is the left child of 9.

But it's also the first that would require restructuring the Tree (to fit it between 9 and 12). To me it looks like the last picture is half-way such a restructuring. Are we seeing the end of the story?

Edit

Ok, I didn't read rule 2 completely. It looks like 10 should have become the left-child of 12. There is no good reason for the Insert to take a left branch at the root.

If 10 is the child of either 5 or 9, it stops being a BST or anything else but an unordered binary tree.