Ancestor In Constant Time
You number every node of a binary tree three times: pre[u] is the position of u in the preorder walk, in[u] in the inorder walk, post[u] in the postorder walk. All three arrays are precomputed. Now you want isAncestor(u, w) in , using nothing but these three arrays.
Here is a tiny tree to test candidate rules against:
A
/ \
B C
/ \
D E
| node | pre | in | post |
|---|---|---|---|
| A | 0 | 3 | 4 |
| B | 1 | 1 | 2 |
| C | 4 | 4 | 3 |
| D | 2 | 0 | 0 |
| E | 3 | 2 | 1 |
Which test is true exactly when u is an ancestor of w, counting a node as an ancestor of itself?
Sign in to answer questions and track your progress
Sign In