Home

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Alternate Derivation

Here is an alternate way to derive the relation between locations of x and s. For below discussion, we allow ancestors of a node to include that node itself. We know that any two nodes in a binary tree must have at least one common ancestor. Say, c is the common ancestor of x and s closest to them. During inorder(c), both x and s must get processed. They both cannot get processed during step (1) of inorder(c), because then c’s left-child would be their closest common ancestor, a contradiction. Similarly, they both cannot get processed during the step (3). Also, x and s should not get processed during step (1) and (3) respectively, because step (2) in the middle processes c, but s is the successor of x.

This leaves only below possibilities:

1. x is processed during step (1) and so its successor s must be processed at step (2), meaning c = s. x has to be the last node processed during step (1) of inorder(c = s). In this case, s is an ancestor of x.
2. x is processed at step (2) and so its successor s must be processed during step (3), meaning c = x. s has to be the first node processed during step (3) of inorder(c = x). In this case, x is an ancestor of s.

(The second possibility corresponds to the case of last section with x having the right-child, and first possibility corresponds to x having no right-child.)

By earlier conclusions on page §, we already know how to locate the first and last node processed during inorder() call of any node.

We can use similar reasoning to locate the next processed node after a given node during Preorder and Postorder Tree Walks.

References

[Prev]   [Up]   

Copyright © 2020 Nitin Verma. All rights reserved.