Blog

Unlike linear data structures (arrays, linked list, queues, stacks, etc.) which have only one logical way to traverse them but trees can be traversed in different ways. The following are commonly used methods for traversing trees.

Preorder Traversal of above tree (Root, Left, Right) : 1 2 4 5 3

Preorder Traversal Steps:

1) Visit the root node
2) traverse the left sub-tree in pre-order
3) traverse the right sub-tree in pre-order

Example – Program to traverse a tree in PreOrder without Recursion 

import java.util.Stack;

public class PreOrderTraversal {

  public static void main(String[] args) throws Exception {

    Tree bt = new Tree();
    Tree.TreeNode root = new Tree.TreeNode("1");
    bt.root = root;
    bt.root.left = new Tree.TreeNode("2");
    bt.root.left.left = new Tree.TreeNode("4");

    bt.root.left.right = new Tree.TreeNode("5");
    bt.root.right = new Tree.TreeNode("3");

    bt.preOrderWithoutRecursion();

  }

}

class Tree {
  static class TreeNode {
    String data;

    TreeNode left, right;

    TreeNode(String value) {
      this.data = value;
      left = right = null;
    }

    boolean isLeaf() {
      return left == null ? right == null : false;
    }

  }

  TreeNode root;


  public void preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<TreeNode>();
    nodes.push(root);

    while (!nodes.isEmpty()) {
      TreeNode current = nodes.pop();
      System.out.printf("%s ", current.data);

      if (current.right != null) {
        nodes.push(current.right);
      }
      if (current.left != null) {
        nodes.push(current.left);
      }
    }
  }

}

Output

1 2 4 5 3