Program to Perform the Inorder Tree Traversal
Below is the Program to Perform the Inorder Tree Traversal:
// Node class representing a single node of a binary tree
class Node {
int data; // Data element stored in the node
Node left, right; // Pointers to left and right child
// Constructor to create a new node with given data
public Node(int item) {
data = item;
left = right = null; // Initially, left and right children are set to null
}
}
// BinaryTree class that defines a binary tree
class BinaryTree {
Node root; // Root of the binary tree
// Constructor to create an empty binary tree with root set to null
BinaryTree() {
root = null;
}
// Recursive function to perform inorder traversal of the tree
void inorderTraversal(Node node) {
if (node == null)
return; // Base case: if current node is null, return
inorderTraversal(node.left); // Recursively traverse the left subtree
System.out.print(node.data + " "); // Visit the current node (print the node's data)
inorderTraversal(node.right); // Recursively traverse the right subtree
}
// Main method to run the code
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(); // Create an instance of BinaryTree
tree.root = new Node(1); // Set root of the tree
tree.root.left = new Node(2); // Set left child of root
tree.root.right = new Node(3); // Set right child of root
tree.root.left.left = new Node(4); // Set left child of node 2
tree.root.left.right = new Node(5); // Set right child of node 2
// Perform inorder traversal and print the output
System.out.println("Inorder traversal of binary tree is: ");
tree.inorderTraversal(tree.root);
}
}
Output
Inorder traversal of binary tree is: 4 2 5 1 3
Time and Space Complexity
- The time complexity of the inorder traversal is O(n), where n is the number of the nodes in binary tree.
- The space complexity of the inorder traversal is O(log n).
Application of the Binary Trees and Inorder Traversal
- It can applies on the Binary Search tree and used to maintain the sorted stream of the data.
- It can be used in the Syntax tree and used in the compilers to represent the syntax of the programs.
- It can be used in the Heap trees and used in the priority queues for the efficient implementation of the algorithms.
Java Program to Perform the Inorder Tree Traversal
The binary tree is the hierarchical data structure in which each node has at most two children and it can referred to as the left child and the right child. Inorder tree traversal is one of the fundamental ways to visit all the nodes in the binary tree. It can specifically visiting the nodes in the left-root-right order.