Preorder traversal of ternary tree

Question

I need to perform a preorder traversal of a ternary tree. I'm familiar with this traversal on a binary tree, such as:

public void preorder(){

   System.out.println(data); 
   if (left != null)
      left.preorder();
   if (right != null)
      right.preorder();
}

This traverses in the order Root, Left, Right. I am confused as to how to do this with a middle child node added. If anyone could explain this that would be great. thanks

Answer 1

General preorder traversal of n-ary tree goes as follows:

• Traverse the node itself
• If exists, traverse child₀
• If exists, traverse child₁
• ...
• If exists, traverse child_n

Binary tree happens to have only child₀ (left) and child₁ (right), but ternary tree also has a middle. So your traversal would have an extra statement between traversing the left and the right subtree:

if (middle != null)
    middle.preorder();