Nick Castello
Nick Castello

Reputation: 51

Preorder traversal of ternary tree

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

Upvotes: 1

Views: 4335

Answers (2)

ravthiru
ravthiru

Reputation: 9663

Traverse middle node between left and right node

public void preOrder(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(" " + node.data);
    preOrder(node.left);
    preOrder(node.middle);
    preOrder(node.right);
}

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727137

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

  • Traverse the node itself
  • If exists, traverse child0
  • If exists, traverse child1
  • ...
  • If exists, traverse childn

Binary tree happens to have only child0 (left) and child1 (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();

Upvotes: 2

Related Questions