Tree traversal: Difference between revisions

Revision as of 17:21, 18 September 2004

Revision as of 17:26, 18 September 2004

Line 22:

</pre>

Finally, anAn '''in-order''' traversal, as above, visits each node between the nodes in its left subtree and the nodes in its right subtree. This is a particularly common way of traversing a [[binary search tree]], because it gives the values in increasing order.

To see why this is the case, note that if <i>n</i> is a node in a binary search tree, then everything in <i>n</i>'s left subtree is less than <i>n</i>, and everything in <i>n</i>'s right subtree is greater than or equal to <i>n</i>. Thus, if we visit the left subtree in order, using a recursive call, and then visit <i>n</i>, and then visit the right subtree in order, we have visited the entire subtree rooted at <i>n</i> in order.

If instead we visit the right subtree, then the current node, then the left subtree, this produces the opposite order as in-order traversal, sometimes called a '''reverse in-order''' or '''reverse-order''' traversal.

<table>