The problem gives the following in-order and pre-order traversal of a binary tree:
In-order: 10 20 30 40 50 60 70 80
Pre-order: 40 50 20 80 30 70 60 10
I am supposed to construct the binary tree that would produce these traversals. I have tried to use the very sensible algorithm from here, but it doesn't seem to be working.
I know that the root node must be 40, because it comes first in the pre-order traversal. From the in-order traversal, I know that 10 20 30 must be in the left sub-tree, and 50 60 70 80 must be in the right sub-tree.
However, the second element in the pre-order traversal is 50. 50 is supposed to be in the right sub-tree, but pre-order traverses the left subtree first. Surely one of 10 20 30 must come second in the pre-order traversal?
What am I doing wrong here?