Inorder Traversal
Tree traversal is a type of graph traversal and refers to visiting every node in the tree. There are various methods for traversing the tree. One of the popular traversal methods is inorder traversal which follows the rule of visiting the left subtree (first), the root of the tree and then the right subtree.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
class Tree {
public class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
left = right = null;
}
}
In this above tree class with inner node class has one instance member data and two objects of Node class left and right. For every new node, we use Node(int data ) constructor to assign data to that node and set left and right as null.
Tree.Node t = new Tree().new Node(1);
t.left = new Tree().new Node(2);
t.left.left = new Tree().new Node(4);
t.left.right = new Tree().new Node(5);
t.right = new Tree().new Node(3);
Algorithm :
- Traverse the left subtree
- Visit the root
- Traverse the right subtree
Inorder traversal for the tree is: 4 2 5 1 3
Program for iterative inorder traversal:
public void inorder(Node root) {
Stack<Node> s = new Stack<>();
Node temp = root;
while (temp != null || s.size() > 0) {
while (temp != null) {
s.push(temp);
temp = temp.left;
}
temp = s.pop();
System.out.print(temp.data + " ");
temp = temp.right;
}
}
In the above program, the stack is used to hold the node data and temp reference to traverse
till the end of the left subtree and printing it, changing the temp address to it's right and
traversing it.
I hope you guys liked this article, here are some other articles you may like:
){kind=link}
0 Comments