0

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?

TookieWookie
  • 165
  • Are you talking about binary search tree? I suppose so. In this case you are not wrong, these two visits are not possible. 40 is the root, then we visit left and print the left element, but the next one is 50 and 50>40, so this is not the left subtree. Then, the left subtree is empty and 50 is the right son of the root. But at this point 20 has to be a child of 50, which is to the right of 40. Impossible. – SilvioM Nov 07 '22 at 22:05
  • @SilvioM, no, it's just a regular binary tree. – TookieWookie Nov 07 '22 at 22:09
  • The first node of in-order is $10$ which is in the left sub-tree, but it is also the last node in pre-order which is in right sub-tree. This is a conflict. Please check the original source if it as really as you have it here. – Somos Nov 07 '22 at 22:33
  • @SilvioM Double and triple-checked. The problem is just self-contradictory then – TookieWookie Nov 07 '22 at 22:42
  • @SilvioM The problem starts with the inorder sequence, and then programmatically randomly shuffles the inorder sequence to produce the pre-order sequence. Surely this is not guaranteed to produce sensible results, right? – TookieWookie Nov 08 '22 at 12:55

0 Answers0