3
$\begingroup$

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:

enter image description here

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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.
$\endgroup$
9
  • 1
    $\begingroup$ This solution assumes that both children are present, am I correct? $\endgroup$ Apr 11, 2022 at 0:20
  • $\begingroup$ I am sorry, I don't see how we can determine the size of the left child of u in constant time using pre-order. I can imagine some algorithms with higher time complexity thought. $\endgroup$
    – Rodrigo
    Apr 11, 2022 at 9:37
  • $\begingroup$ @HendrikJan You are correct, but I'll be honest, I can't find a good solution when there is only one child :/ $\endgroup$
    – Nathaniel
    Apr 11, 2022 at 17:22
  • $\begingroup$ @Nathaniel Yes, I tried very hard too, but now I am convinced that no such solution exists. If there is a long linear path with single children at each level then the wanted information must come from far. Guess that was overlooked. in the question, and this is the best we can do! $\endgroup$ Apr 11, 2022 at 17:42
  • 1
    $\begingroup$ @Nathaniel Great answer! I wish I could upvote more. Here is one suggestion. For the first few seconds, it is hard for me to see the outline of this answer. Does it fully solve the exercise? Apparently, this answer says the exercise is wrong in "constant time". Or is it? A reader has to read all the ways through to see what is going on and is still not quite sure. My suggestion is to add some headers, some section separators, some easy-to-find summaries so that a readers like me can find information very quickly. $\endgroup$
    – John L.
    Apr 13, 2022 at 15:43

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.