0
$\begingroup$

What is the number of binary trees which have the same X-order and Y-order as the given tree?

Example:

X-order: POSTORDER(T) = POSTORDER(TL) POSTORDER(TR) root

Y-order: ANTIORDER(T) = ANTIORDER(TR) ANTIORDER(TL) root

For example, tree T has 9 nodes and its

POSTORDER is : FHECIGDBA

ANTIORDER is: IGDBHEFCA

The specialized question is how many trees are there with 9 nodes that have the given POSTORDER and ANTIORDER. How to start?

$\endgroup$

1 Answer 1

1
$\begingroup$

The general question looks hard. The particular question, however, isn’t too bad.

Clearly $A$ is the root of $T$. From the postorder we can see that $B$ is the root of the right subtree, and from the antiorder we can see that $C$ is the root of the left subtree. Thus, the left subtree must contain the nodes $F,H,E$, and $C$, while the right subtree contains the nodes $I,G,D$, and $B$.

Look at the right subtree. Its postorder is $IGDB$, and its antiorder is also $IGDB$. If this subtree has a right subtree, its root must be $D$, and if it has a left subtree, its root must be $D$. Thus, it has either a left or a right subtree, but not both. Similar reasoning will show you that the subtree $IGDB$ must be a chain; I’ve illustrated two of the possibilities below, and it’s not hard to see how many chains are possible.

              B                    B  
             /                      \  
            D                        D  
           /                        /  
          G                        G  
           \                        \  
            I                        I

Now look at the left subtree of $T$. Its postorder is $FHEC$, and its antiorder is $HEFC$. Since $E$ and $F$ are different, this subtree has both a left and a right subtree; the root of the right subtree is $E$, and the root of the left subtree is $F$. You should have no trouble deciding in which subtree $H$ goes and in how many different ways it can be placed.

Now just multiply the number of possible right subtrees by the number of possible left subtrees to get the number of possible trees $T$ for this particular pair of post- and antiorder.

Added: The general case isn’t as bad as I thought. Let $T$ be a binary tree with $k$ nodes that have one child. It’s not hard to see that at each of those $k$ nodes you can (independently) make the child either a left child or a right child without affecting the post- or antiorder of the tree. Thus, there are at least $2^k$ trees with the same post- and antiorders as $T$. Moreover, the nodes with single children are easily identified from the combination of post- and antiorder. Every node $v$ it the root of some subtree; look at the nodes immediately preceding it in the post- and antiorders, if there are any: if they are identical, say $u$, then $u$ is the single child of $v$. In the example that picks out nodes $B,D,G$, and $E$.

If, on the other hand, $v$ has distinct immediate predecessors in the two orders, say $x$ in postorder and $y$ in antiorder, then $y$ must be the left and $x$ the right child of $v$ in any tree with these post- and antiorders; no variation is possible. Thus, the only points at which the reconstruction of $T$ from the two orders is ambiguous is in choosing the side for single children.

$\endgroup$
2
  • $\begingroup$ I know that the general formula for that particular case (postorder and antiorder) is $2^k$ where $k$ is the number of parent nodes with 1 child. Can that help with discovering the solution? $\endgroup$
    – user58233
    Nov 21, 2013 at 17:56
  • $\begingroup$ @user58233: It turns out that I can, but it will take me a few minutes to write up. $\endgroup$ Nov 21, 2013 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .