This post shows you about Binary Tree Traversal in Java programming language. Using inorder, preorder and postorder algorithm to traverse a tree means visiting every node in the tree. Not like linear data structures (arrays, stacks, queues, linked list) have only one way to visit. But a hierarchical data structure like a tree can be traversed in some ways.
Binary Tree Traversal in Java
Three ways of traversal (Depth First Traversals)
Inorder traversal algorithm
- First, visit all the nodes in the left subtree
- Then visit the root node
- Visit all the nodes in the right subtree
Following the order from 1 to 4 in the above image, you have the list of nodes: 40, 20, 50, 10, 30
Application of Inorder Traversal: If a tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, then an Inorder traversal should be used. The tree would be flattened in the same way it was created.
Preorder Traversal algorithm
- Visit root node
- Traversal all the nodes in the left subtree
- Traversal all the nodes in the right subtree
Following the order from 1 to 4 in the above image, you have the list of nodes: 10, 20, 40, 50, 30
Application of Preorder Traversal: If you need to explore the roots before inspecting any leaves, you pick Preorder because you will encounter all the roots before all of the leaves.
Postorder Traversal algorithm
- Traversal all the nodes in the left subtree
- Traversal all the nodes in the right subtree
- Visit the root node
Following the order from 1 to 4 in the above image, you have the list of nodes: 40, 50, 20, 30, 10.
Application of Postorder Traversal: If you need to explore all the leaves before any nodes, you select
Postorder because you don’t waste any time inspecting roots in search for leaves.
Implement a Binary Tree Traversal in Java
Here is a simple java program that demos three ways to visit a tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
/* Simple Java program for three ways of tree traversal */ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } class BinaryTreeDS { // Root of Binary Tree Node root; BinaryTreeDS() { root = null; } // Visit its nodes in postorder (left,right,root) void visitPostorder(Node node) { if (node == null) return; //1. First recur on left subtree visitPostorder(node.left); //2.Recur on right subtree visitPostorder(node.right); //3. Print the current node System.out.print(node.data + " "); } /* Visit its nodes in inorder - (left,root,right)*/ void visitInorder(Node node) { if (node == null) return; //1. First recur on left child visitInorder(node.left); //2. Print the left current node System.out.print(node.data + " "); //3. Recur on right child visitInorder(node.right); } /* Visit its nodes in preorder - (root,left,right)*/ void visitPreorder(Node node) { if (node == null) return; //1. First print the current node System.out.print(node.data + " "); //2. Recur on left sutree visitPreorder(node.left); //3. Recur on right subtree visitPreorder(node.right); } // Main method public static void main(String[] args) { BinaryTreeDS tree = new BinaryTreeDS(); tree.root = new Node(10); tree.root.left = new Node(20); tree.root.right = new Node(30); tree.root.left.left = new Node(40); tree.root.left.right = new Node(50); System.out.println("Inorder traversal results: "); tree.visitInorder(tree.root); System.out.println("\nPreorder traversal results: "); tree.visitPreorder(tree.root); System.out.println("\nPostorder traversal results: "); tree.visitPostorder(tree.root); } } |
Running the above program, you get the output like this:
Time Complexity
Because you traverse each node once in a binary tree with n nodes. While the amount of work you do for each node is constant (does not depend on the rest of the nodes). So time complexity is O(n)
That’s all about Binary Tree Traversal in Java.
References
Binary Tree Data Structure in Java
Binary Tree Java Documentation
