The traversal of a BST

Question

I need your help Is it possible to have a binary search tree which pre-order and in-order traversals generate the same result ?

I've tried to take an example tree consisting of 7 nodes , and i labeled the nodes from a to g .. this is my tree :

         a
    b          c 
 d     e    f     g 

where a is the root , b and c are its children , d and e are b's childrens , and f and g are c's children

The pre-order traversal gives this result : a b d e c f g
The in-order traversal gives this result : d b e a f c g

So in order to get the same result i need that a = d = e and f = c .. which is not possible since it is a BST ..

Could you just check if it was correct ? And if my idea about traversals is correct ?

Regards ,

Answer 1

If you have a tree with only right children(i.e. a list) you will have its preorder being equal to its inorder traversal.

Answer 2

This sounds like homework, so I won't go into too much detail. But yes, it is possible to have a binary tree with identical pre- and in-order traversals. Consider how you might make one with two nodes. Then consider how you might make one with three.