In a traversal of a binary tree, each element of the binary tree is visited exactly once.
During the visit of an element, all action (make a clone, display, evaluate the operator, etc.) with respect to this element is taken.
Binary Tree Traversal Methods
Preorder
Inorder
Postorder
Level order
Preorder Traversal
t is the root of the subtree being traversed.
Preorder Example (visit = print)
a b c a b c
Preorder Example (visit = print)
a b c d e f g h i j a b d g h e i c f j
During the traversal, t starts at the root, moves to the left child b of the root, then to the left child d of b. When the traversal of the left subtree of b is complete, t, once again, points to the node b. The t moves into the right subtree of b. When the traversal of this right subtree is complete, t again points to b. Following this, t points to a. We see that t points to every node in the binary tree three times – once when you get to the node from its parent (or in the case of the root, t is initially at the root), once when you return from the left subtree of the node, and once when you return from the node’s right subtree. Of these three times that t points to a node, the node is visited the first time.
Preorder Of Expression Tree
+ a b - c d + e f * / Gives prefix form of expression! / * + a b - c d + e f
Inorder Traversal
Inorder Example (visit = print)
a b c b a c
Inorder Example (visit = print)
a b c d e f g h i j g d h b e i a f j c
Inorder By Projection (Squishing)
a b c d e f g h i j g d h b e i a f j c
Inorder Of Expression Tree
+ a b - c d + e f * / Gives infix form of expression (sans parentheses)! e a + b * c d / + f -
Postorder Traversal
Postorder Example (visit = print)
a b c b c a
Postorder Example (visit = print)
a b c d e f g h i j g h d i e b j f c a
Postorder Of Expression Tree
+ a b - c d + e f * / Gives postfix form of expression! a b + c d - * e f + /
Traversal Applications
a b c d e f g h i j Make a clone.
Determine height.
Determine number of nodes.
Make a clone using postorder traversal … clone the left subtree, clone the right subtree, clone the root in the visit step.
Determine height using postorder traversal … determine the height of the left subtree, determine the height of the right subtree, in the visit step add 1 to the max of the already determined heights of the left and right subtrees.
Determine number of nodes using preorder, inorder, or postorder traversal … initialize a counter to 0, add 1 to the counter in the visit step.
Level Order
Level-Order Example (visit = print)
a b c d e f g h i j a b c d e f g h i j
Binary Tree Construction
Suppose that the elements in a binary tree are distinct.
Can you construct the binary tree from which a given traversal sequence came?
When a traversal sequence has more than one element, the binary tree is not uniquely defined.
Therefore, the tree from which the sequence was obtained cannot be reconstructed uniquely.
Some Examples
a b a b inorder = ab b a a b postorder = ab b a b a level order = ab a b a b preorder = ab
Comments