Binary Tree preorder traversal understanding

Question

This homework assignment ask me to write the preorder traversal of the tree but I'm confuse on how this would work because it visit node, left subtree, right subtree but it doesn't go to the middle. Would it just skip it or give an error? or do i just ignore the middle one?

Answer 1

That's not a binary tree

Binary is english for 'related to 2'. Hence, a binary tree is a tree such that any node is either A leaf (has no children), or, it has exactly 2 children. Essentially, all nodes have either 0 or 2 children.

Your picture isn't a binary tree: Node D has 3 children. Node B has only 1.

But you can pre-order traversal just fine

pre-order traversal has nothing to do with specifically binary trees. It's an algorithm that.. applies to trees. There is no need for the tree to be a binary tree.

To pre-order this one:

1. Start at the root.
2. Emit the value of the currently 'selected' node.
3. Go through the children it has in left-to-right order. For each child, recursively apply this algorithm at step 2.

That's all you have to do here. Applying that here:

1. Start at the root.
2. Emit its value: We have "A"
3. Loop through its direct children - apply this algorithm to B and C.

the recursion to B would end up printing "BDHIJ", the recursion into C would print "CEG". The end result is "ABDHIJCEG".

There's no such thing as 'skipping the middle node' unless you are reading some tutorial or explanation that says 'first iterate the left side, then, iterate the right side'. Those terms ('left side' and 'right side') presume a binary tree. There is no mention of 'the middle node' because the explanation assumes a binary tree; binary trees don't have middle nodes.

Some traversals, such as in-order, do not apply to non-binary trees. That's because they visit the left, then the node itself, then the right. This does not 'make sense' for non-binary trees. But, pre-order doesn't do that, therefore, can trivially be expanded to N-ary trees.