- Given a binary tree, traverse the binary tree using recursive algorithm.
- Binary tree traversal is categorized into two parts.
- Depth first search traversal (recursive algorithm)
- Pre Order Traversal
- Post Order Traversal
- In Order Traversal
- Breadth First search (BFS) or Level Order Traversal (non-recursive) algorithm.
- Depth first search traversal (recursive algorithm)
Applications of depth first search:
- Delete all nodes in binary tree using PostOrder traversal
- Find InOrder successor in BST using InOrder traversal
- Find InOrder predecessor in BST using InOrder traversal
Examples of PreOrder, PostOrder & InOrder (DFS) algorithm (java).
Example 1 (PreOrder binary tree traversal):
- In preOrder traversal:
- We are visit current node, then
- We visit left child node, then
- We visit right child node.
- We have shown the preOrder traversal in Fig. 2:
- Visit parent node or current node
- Visit left child
- Visit right child
PreOrder binary tree traversal of binary tree shown in Fig 3 is:
60 20 10 30 80 70 65 75 90 85 95
public static void preOrder(Node root) { if (null == root) { return; } System.out.printf("%d ", root.data); preOrder(root.left); preOrder(root.right); }
Example 2 (PostOrder binary tree traversal):
- In postOrder traversal:
- We visit left child, then
- We visit right child, then
- We visits current node.
- We have shown the postOrder traversal in Fig. 4:
- Visit left child
- Visit right child
- Visit parent node or current node
PostOrder binary tree traversal of binary tree shown in Fig 5 is:
10 30 20 65 75 70 85 95 90 80 60
public static void postOrder(Node root) { if (null == root) { return; } postOrder(root.left); postOrder(root.right); System.out.printf("%d ", root.data); }
Example 3 (InOrder binary tree traversal):
- Using InOrder traversal:
- We first visits the left child, then
- Current node, then
- Right child of binary tree.
- We have shown the inOrder traversal in Fig. 6:
- Visit left child
- Visit parent node or current node
- Visit right child
InOrder binary tree traversal of binary tree shown in Fig 7 is:
10 20 30 60 65 70 75 80 85 90 95
public static void inOrder(Node root) { if (null == root) return; inOrder(root.left); System.out.printf("%d ", root.data); inOrder(root.right); }
Time complexity of algorithm is O(n).
Program: traverse binary tree in PreOrder, PostOrder & InOrder using java
1.) DFSTraversal Class:
DFSTraversal class performs the following operations:
- preOrder traversal
- postOrder traversal
- inOrder traversal
package org.learn.Question; public class DFSTraversal { public static void preOrder(Node root) { if (null == root) { return; } System.out.printf("%d ", root.data); preOrder(root.left); preOrder(root.right); } public static void postOrder(Node root) { if (null == root) { return; } postOrder(root.left); postOrder(root.right); System.out.printf("%d ", root.data); } public static void inOrder(Node root) { if (null == root) return; inOrder(root.left); System.out.printf("%d ", root.data); inOrder(root.right); } }
2.) Node Class:
- Node class is represents the nodes of a binary tree.
package org.learn.Question; public class Node { public int data; public Node left; public Node right; public Node(int num) { this.data = num; this.left = null; this.right = null; } public Node() { this.left = null; this.right = null; } public static Node createNode(int number) { return new Node(number); } }
3.) App Class:
- We are creating the binary tree in main method.
- We are calling the method of DFSTraversal class to perform preOrder, postOrder and inOrder traversal.
package org.learn.Client; import org.learn.Question.DFSTraversal; import org.learn.Question.Node; public class App { public static void main(String[] args) { // root level 0 Node A = Node.createNode(60); // Level 1 Node B = Node.createNode(20); Node C = Node.createNode(80); // Level 2 Node D = Node.createNode(10); Node E = Node.createNode(30); Node F = Node.createNode(70); Node G = Node.createNode(90); // Level 3 Node H = Node.createNode(65); Node I = Node.createNode(75); Node J = Node.createNode(85); Node K = Node.createNode(95); // connect Level 0 and 1 A.left = B; A.right = C; // connect level 1 and level 2 B.left = D; B.right = E; C.left = F; C.right = G; // connect level 2 and level 3 F.left = H; F.right = I; G.left = J; G.right = K; System.out.println("PreOrder binary tree traversal :"); DFSTraversal.preOrder(A); System.out.println("\nPostOrder binary tree traversal :"); DFSTraversal.postOrder(A); System.out.println("\nInOrder binary tree traversal : "); DFSTraversal.inOrder(A); } }
Output: preOrder, PostOrder & InOrder binary tree traversal using java
PreOrder binary tree traversal : 60 20 10 30 80 70 65 75 90 85 95 PostOrder binary tree traversal : 10 30 20 65 75 70 85 95 90 80 60 InOrder binary tree traversal : 10 20 30 60 65 70 75 80 85 90 95
Download Code – binary tree traversal algorithm (pre,post & inorder)