Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees.
Depth First Traversals: (a) Inorder (Left, Root, Right) : 4 2 5 1 3 (b) Preorder (Root, Left, Right) : 1 2 4 5 3 (c) Postorder (Left, Right, Root) : 4 5 2 3 1 // Java program for different tree traversals class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void Postorder(Node node) { if (node == null) return; Postorder(node.left); Postorder(node.right); System.out.print(node.key + " "); } void Inorder(Node node) { if (node == null) return; Inorder(node.left); System.out.print(node.key + " "); Inorder(node.right); } voidPreorder(Node node) { if (node == null) return; System.out.print(node.key + " "); Preorder(node.left); Preorder(node.right); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); System.out.println("Preorder traversal of binary tree is "); tree. Preorder(root); System.out.println("\nInorder traversal of binary tree is "); tree. Inorder(root); System.out.println("\nPostorder traversal of binary tree is "); tree. Postorder(root); } }