The resulting traversal method called the euler tour traversal

The inorder traversal can also be applied to the problem of computing a drawing of a binary tree. We can draw a binary tree T with an algorithm that assigns x- and y-coordinates to a node v of T using the following two rules (see Figure 7.19):

• x(v) is the number of nodes visited before v in the inorder traversal of T

The Euler Tour Traversal of a Binary Tree

The tree-traversal algorithms we have discussed so far are all forms of iterators. Each traversal visits the nodes of a tree in a certain order, and is guaranteed to visit each node exactly once. We can unify the tree-traversal algorithms given above into a single framework, however, by relaxing the requirement that each node be visited exactly once. The resulting traversal method is called the Euler tour traversal, which we study next. The advantage of this traversal is that it allows for more general kinds of algorithms to be expressed easily.

423

if v is external, then these three "visits" actually all happen at the same time. We describe the Euler tour of the subtree rooted at v in Code Fragment 7.26.

The running time of the Euler tour traversal of an n-node tree is easy to analyze, assuming each visit action takes O(1) time. Since we spend a constant amount of time at each node of the tree during the traversal, the overall running time is O(n).