Let the rank of a position p during traversal be defined such that the first ele
ID: 3763141 • Letter: L
Question
Let the rank of a position p during traversal be defined such that the first element visited has rank 1, the second element visited has rank 2, and so on. For each position p in a tree T, let pre(p) be the rank of p in a preorder traversal of T, let post(p) be the rank of p in a postorder traversal of T, let depth (p) be the depth of p, and let desc(p) be the number of descendants of p, not counting p itself. Derive a formula defining post(p) in terms of desc(p), depth(p), and pre(p), for each node p in T.
Explanation / Answer
Assume a tree as shown below:
The pre-order of the above tree is: 2, 1, 3
Rank of 1 in Pre(2)=1
Rank of 2 in Pre(1)=2
Rank of 3 in Pre(3)=3
Dep(p)_Depth of tree is the number of edges form current node to root.
Depth(1)=0
Depth(2)=1
Depth(3)=1
Desc(1)=2
Desc(2)=0
Desc(3)=0
Desc(p)-Descendants of a tree is unique path between current a root node.
The post order of the above tree is 1, 3, 2.
Post (p) can be derived using pre(p), desc(p) and depth(p).
Post(2)=3 if we follow the post-order.
Post(p)=[pre(2)+desc(2)]-depth(2)
=(1+2)-0;
=3
Hence it is proved that
Post(p)= [pre(p)+desc(p)]-depth(p);
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.