If you have a tree with only right children(i.e. a list) you will have its preorder being equal to its inorder traversal.
The traversal of a BST
-
04-07-2022 - |
Pregunta
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 ,
Solución
Otros consejos
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.