Traversal
Traversal is the process of visiting and examining all nodes in a binary tree in a specific order. There are three commonly used traversal methods: inorder traversal, preorder traversal, and postorder traversal.
Inorder Traversal: In inorder traversal, the left subtree is visited first, then the root node, and finally the right subtree. The inorder traversal visits the nodes in ascending order of their keys.
Preorder Traversal: In preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree.
Postorder Traversal: In postorder traversal, the left subtree is visited first, then the right subtree, and finally the root node.
Here is an example of performing these traversal methods on a binary tree in Java:
1import java.util.LinkedList;
2
3public class TraversalExample {
4
5 static class TreeNode {
6 int val;
7 TreeNode left;
8 TreeNode right;
9
10 TreeNode(int val) {
11 this.val = val;
12 }
13 }
14
15 public static void main(String[] args) {
16 // Create a binary tree
17 TreeNode root = new TreeNode(1);
18 root.left = new TreeNode(2);
19 root.right = new TreeNode(3);
20 root.left.left = new TreeNode(4);
21 root.left.right = new TreeNode(5);
22
23 // Perform inorder traversal
24 System.out.println("Inorder Traversal:");
25 inorderTraversal(root);
26
27 // Perform preorder traversal
28 System.out.println("Preorder Traversal:");
29 preorderTraversal(root);
30
31 // Perform postorder traversal
32 System.out.println("Postorder Traversal:");
33 postorderTraversal(root);
34 }
35
36 // Inorder Traversal
37 static void inorderTraversal(TreeNode node) {
38 if (node == null) {
39 return;
40 }
41
42 inorderTraversal(node.left);
43 System.out.print(node.val + " ");
44 inorderTraversal(node.right);
45 }
46
47 // Preorder Traversal
48 static void preorderTraversal(TreeNode node) {
49 if (node == null) {
50 return;
51 }
52
53 System.out.print(node.val + " ");
54 preorderTraversal(node.left);
55 preorderTraversal(node.right);
56 }
57
58 // Postorder Traversal
59 static void postorderTraversal(TreeNode node) {
60 if (node == null) {
61 return;
62 }
63
64 postorderTraversal(node.left);
65 postorderTraversal(node.right);
66 System.out.print(node.val + " ");
67 }
68}xxxxxxxxxx}import java.util.LinkedList;public class TraversalExample { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } public static void main(String[] args) { // Create a binary tree TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); // Perform inorder traversal System.out.println("Inorder Traversal:"); inorderTraversal(root); // Perform preorder traversal System.out.println("Preorder Traversal:"); preorderTraversal(root);