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!

Improve this question
$\endgroup$
1
  • $\begingroup$ Please credit the original source of all copied/quoted material: cs.stackexchange.com/help/referencing $\endgroup$ Commented May 28, 2022 at 20:09

1 Answer 1

Reset to default
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".

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.