2
$\begingroup$

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!

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.