Question

If x is a node in a hierarchically organized tree structure, then it is

________________________________ for all nodes in the tree structure higher than it.

Answer 1

Answer:

If x is a node in a hierarchically organized tree structure, then it is placed in the lower-most left for all nodes in the tree structure higher than it.

Description:

In a tree, take any two nodes x and y neither of which is an ancestor of the other. As a consequence of the definition of “to the left,” one of x and y will be to the left of the other. To tell which, follow the paths from x and y toward the root. At some point, perhaps at the root, perhaps lower, the paths will meet at some node z as suggested by Fig. 5.2. The paths from x and y reach z from two different nodes m and n, respectively; it is possible that m = x and/or n = y, but it must be that m 6 = n, or else the paths would have converged somewhere below z .

r

z

m n

x y

Fig. 5.2. Node x is to the left of node y.

Suppose m is to the left of n. Then since x is in the subtree rooted at m and y is in the subtree rooted at n, it follows that x is to the left of y. Similarly, if m were to the right of n, then x would be to the right of y.