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.
