# Solution Verification: How does the postorder traversal of a BST change after rotating left?

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?

My Attempt:
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!

"In order for the traversal order not to change (after the rotation), we need to have" \begin{aligned} &postOrder(a), postOrder(b), postOrder(c), y, x \\ =\ &postOrder(a), postOrder(b), x, postOrder(c), y. \end{aligned}
Suppose $$postOrder(c) = u_1, u_2, \cdots, u_k$$, $$k\ge0$$. Then $$u_1, u_2, \cdots, u_k, y, x = x, u_1, u_2, \cdots, u_k, y,$$ which means $$x=u_1=u_2=\cdots=u_k=y=x$$. So we must have $$x$$, $$y$$ and, if $$y$$ has a right child, all nodes of the subtree rooted the right child of $$y$$ are the same.