Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$.
How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the traversal not change?
I've decided to draw a sketch of the sub-tree of $T$ rooted in $x$:
x / \ a y / \ b c
Where a,b,c are whatever subtrees/nodes rooted under $y$ and $x$.
The postorder traversal of this subtree is: $postOrder(a), postOrder(b), postOrder(c), y, x$.
After rotating the subtree on node x we will get:
y / \ x c / \ a b
And now the post order traversal will be: $postOrder(a), postOrder(b), x, postOrder(c), y$.
So in order for the traversal order not to change (after the rotation), we need to have:
$postOrder(c) = x$
$postOrder(c) = y$
$x = y$
Which means we must have a tree that looks like this:
x / \ a x / \ b x
So in order for the postOrder traversal not to change (after the rotation) we must have 3 equal nodes on the right side of this subtree.
I would really appreciate any feedback on my solution attempt, thanks in advance!