Binary Search Tree Traversals

Question

I have a clue as to how this code/traversals work but I'm still confused.

For example, in the first traversal (Preorder), it prints 31, 12, 25 but then it backtracks all the way to 68? How does it know to do this? My professor referenced a stack but I am still a bit confused.

As for the other codes, I don't know how to backtrack on them at all. I understand the first one quite a bit but for the next 2, not so much.

Answer 1

The rules for traversing a tree are, to visit all nodes of a tree you do this:

• Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the nodes in the right subtree of the root. In steps (2) and (3), use the same rule as above.
• Inorder: (1) visit all the nodes in the left subtree, (2) visit the root node, (3) visit all the nodes in the right subtree.
• Postorder: (1) visit all the nodes in the left subtree, (2) visit all the nodes in the right subtree, (3) visit the root.

For example, to do an inorder traversal of your tree,

1. Visit the nodes, $(12, 25)$, in the left subtree.
2. Visit the root, $31$.
3. Visit the node in the right subtree, $(68,50,72,39,56,42,53,60)$

In step (1) we use the same rule: visit the left subtree of 12 (nothing there), then the root, 12, then the right subtree $(25)$. So now you've done task (1), having visited the nodes $12, 25$ in that order.

In step (2) we visit $(31)$, so now we've visited $12,25, 31$.

In step (3) we need to visit the nodes in the right subtree, using the rule Left-Root-Right, as we did before. It turns out that we'll visit the right subtree's nodes in order 39,42,50,53,56,60,72.

Doing this traversal by hand is complicated and prone to error. While computers are easily able to use these recursive rules, humans aren't so good at this. Fortunately, there's a three-step technique that's easy for people to apply.

1. Draw an upward-pointing triangle around each node in your tree.
2. "Shrink-wrap" the whole tree by drawing a closed circuit around the whole tree, making your circuit follow the tree as closely as possible, like this:

3. Starting at the root node, trace the circuit counter-clockwise, listing a node as visited when: for a preorder traversal, you encounter the node for the first time (that is, when you travel along the left side of the node's triangle); for an inorder traversal, mark the node as visited when you encounter the node for the second time (that is, when you travel around the base of the node's triangle); for a postorder traversal, mark the node as visited when you encounter it for the last time (when you travel along the right side of the node's triangle).

Try it for your tree and each of the three traversals and you'll see what happens.

Answer 2

These are recursively defined traversal methods, as you can see from your code. A stack is useful if you want to write an implementation without recursion. Wikipedia has some explanation of the three traversals, and proposes code for the stack implementations.