Preorder and Postorder Tree Walks Consider a binary search t

Preorder and Postorder Tree Walks

Consider a binary search tree. For a node p, denote by p_pre and p_postthe positions of p in the output sequences of Preorder-Tree-Walk and Postorder-Tree-Walk, respectively.

(a) Show that if node q is in node p\'s subtree, then p_pre < q_pre and p_post > q_post.

(b) Is the converse (i.e., if p_pre < q_pre and p_post > q_post, then q is in p\'s subtree) true as well? If so, prove it; otherwise, provide a counter example

Solution

a) By the definition of pre-order traversal, a node p is visited first followed by it\'s left subtree T_1, followed by it\'s right subtree T₂.

Let q be a node such that q belongs to T₁ or T₂ and T₁, T₂ are subtrees of node p. Then, p is always visited before q by the definition of pre-order traversal. Hence ppre < qpre. --------------------------------- (1)

By the definition of post-order traversal, a node p is visited last after visiting it\'s left subtree T₁ and it\'s right subtree T₂ in that order.

As before, if q be a node such that q belongs to T₁ or T₂ and T₁, T₂ are subtrees of node p, then, p is always visited after q by the definition of post-order traversal. Hence ppost > qpost. ---------------------------- (2)

b) The converse is also true. If ppre < qpre, then p is visited before q in pre-order traversal. According to definition the root of a subtree is always visited before the subtree, hence p must be the root of a subtree containing q.

Also, if ppost > qpost, then p is visited after q in post-order traversal. According to definition the root of a subtree is always visited after the subtree, hence p must be the root of a subtree containing q.