Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order.

I believe that I understood the three terms pretty well, and have tried several exercises and examples, which I got right. But I have problems when formulating a relation between these ways of traversing a tree with other properties of the tree.

Take this exercise as an example:

I have tried to draw several binary trees and to imagine some kind of relation between the numbers and the size of the subtrees, but always been unable to.

Thanks for any help in advance! -- This exercise is from Open Data Structures (in pseudocode) from Pat Morin

Long story short: it is possible in constant time if the tree is a full binary tree. If not, there are some cases where there is not enough information to find the size of the subtree in constant time.

Note that you have access to the node of the tree and not only the numbers of the node $u$.

That means that you can check in constant time the pre-, in- and post-order numbers of the left and right child of $u$.

Now you can use the pre-order to find the size of the left child and the post-order to find the size of the right child. Can you see how?
Some vocabulary and details on tree traversal

A bit of vocabulary:

• a descendant $v$ of a node $u$ is a node that appears in the subtree rooted in $u$. A left (resp. right) descendant is a descendant of the left (resp. right) child of $u$;

• an ancestor $u$ of a node $v$ is a node such that $v$ is a descendant of $u$; $u$ is a left (resp. right) of $v$ if $v$ is a right (resp. left) descendant of $u$;

• a cousin $w$ of a node $v$ is a node such that $v$ and $w$ have a common ancestor $u$, different of $v$ and $w$. $w$ is a left (resp. right) cousin of $v$ if $w$ is a left (resp. right) descendant of $u$ and $v$ is a right (resp. left) descendant of $u$.

Now here is an array to know what appears before and after a node $u$ in each order:

Which node
pre-order
in-order
post-order

left ancestor
before
before
after

right ancestor
before
after
after

left descendant
after
before
before

right descendant
after
after
before

left cousin
before
before
before

right cousin
after
after
after

What does that mean? It means that for a node $u$, $u.pre$ (the pre-order number of $u$) is equal to the number of ancestors of $u$ plus the number of left cousins. Similarly, $u.post$ is the number of descendants plus the number of left cousins.

That also means that $u.post - u.pre$ is the number of descendants minus the number of ancestors.
If the tree is a full binary tree, there is a constant time solution

Now let's go back to the problem.

Consider a node $u$. If $u$ has no child, then the size of the subtree is obviously $1$. Otherwise, $u$ has a left child $v$ and a right child $w$. Note that all descendants of $v$ are also left cousins of $w$.

• since $v$ and $w$ have the same number of ancestors, $w.pre - v.pre$ is equal to the size of the subtree rooted in $v$!

• that also means that $w.post - v.post$ is equal to the size of the subtree rooted in $w$ (because the number of descendants of $v$ + left cousins of $v$ is equal to the number of left cousins of $w$).

That means that the size of the subtree rooted in $u$ is:
$$w.pre + w.post - v.pre - v.post + 1$$
If the tree is not full, some conclusions are possible, but there may be problems

Now, as Hendrik Jan pointed it out in the comments, what if $v$ or $w$ doesn't exist?

• if $u$ has only a left child $v$, it is possible to know the size of the right child of $v$, using the in-order number. Indeed, since $u$ has no right child, $u.in - u.post$ is equal to the number of left ancestors of $u$, which is also the number of left ancestors of $v$. That means that the number of right descendants of $v$ is $u.in - v.in - 1$ (since $u.post = v.post + 1$ because $u$ has no right child). Now three cases are possible:

• $v$ has no left child. Since we know the size of the right child, we know the size of the subtrees rooted in $v$ and in $u$ (it is $u.in - v.in + 1$ for the latter);

• $v$ has a left and a right child. Using the previous method, we can find the size of the subtree rooted in $v$ and then the size of the subtree rooted in $u$;

• $v$ has a left child but no right child. In the case, we are stuck as we cannot find any conclusion using only the informations in $u$ and $v$. As an example, here are two trees where a node $u$ has an only left child $v$ and $u$ and $v$ have the same pre-, in- and post- order numbers, but the subtree rooted in $v$ are not of the same size:

1
   / \_________
  2            5
 / \          /
3   4        6
            /
           7
          /
         8

  1
 / \_________
2            4
 \          /
  3        5
          /
         6
        /
       7
        \
         8
          \
           9

In both trees, the node $5$ has a pre-order of $5$, in-order of $8$ and post-order of $7$, and the node $6$ (only left child of $5$ that has only a left child) has a pre-order of $6$, in-order of $7$ and post-order of $6$. However, the subtree rooted in $5$ is of size $4$ in the first tree and of size $5$ in the second tree. That means that knowing only those informations cannot lead to the conclusion. One could find similar examples with a left path as long as wanted.

• Similar conclusions can be done if $u$ has only a right child.

StackExchange Computer Science Q#150553, answer score: 6