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

Question

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!

Answer 1

The sketches of the sub-tree before and after the left rotation are clear.

"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.

---

By the way, postorder traversal of a BST (binary search tree) does not make much sense. We usually perform inorder traversal on a BST, which passes all nodes in the sorted order of the keys. It might be better if "BST" in the exercise is replaced with "binary tree".