How to Do Inorder Traversal in Binary Tree in Java
by ContributorJava doesn't have a binary tree class, though it's simple to present a version of the data structure to do an inorder traversal. A "traversal" of a binary tree is a formulaic procedure for visiting each node on the binary tree one time. An inorder traversal will do this in sorted order. Traversal is often implemented as some sort of iterator (like a list iterator) or by a method that will call a callback method for each node. You can, however, do this without using callbacks or iterators, instead printing to the console each node visited.
Create a basic binary search tree class. At this point, you will only need a basic constructor method that initializes the node's value and an insert method. The insert method will traverse a tree and make a new node in the right place. ""public class BinaryTree {
BinaryTree left;
BinaryTree right;
int value;
public BinaryTree(int v) {
value = v;
}
// Insert a value into the tree
public void insert(int v) {
if(v < value) {
if(left == null)
left = new BinaryTree(v);
else
left.insert(v);
}
else if(v > value) {
if(right == null)
right = new BinaryTree(v);
else
right.insert(v);
}
}
}""
Create the instance (node) of the binary tree that will be the root node. Like any other node, the root node needs to have a value. It's usually best to choose a value close to the median of the objects you're storing, as binary trees should be as balanced as possible. ""BinaryTree b = new BinaryTree(50);""
Insert nodes into the tree in specific order to retain balance, as this binary tree isn't auto-balancing. This example creates the smallest tree possible in order to maintain efficiency.""b.insert(20);
b.insert(40);
b.insert(10);
b.insert(5);
b.insert(45);
b.insert(70);
b.insert(60);
b.insert(80);
b.insert(55);
b.insert(85);""
Move across the tree using an inorder traversal. The left tree is traversed first, followed by the root node, and then the right tree is traversed. Using recursion, the code is merely three lines. However, since recursion takes stack space, it should be used carefully. With a small and balanced binary tree, recursion won't overflow the stack.
Add a new method to the Java BinaryTree class called inorder.""public void inorder() {
if(left != null) left.inorder();
System.out.println(value);
if(right != null) right.inorder();
}""
Call the inorder method after your inserts to print the nodes in sorted order.""b.inorder();"
Tips
- check Methods like a "delete node" method are not supported by this example class.
- check In this example of inorder traversal, the stack will only grow to the height of the tree, so the stack won't overflow. If your binary tree is very large, the traversal function should be implemented iteratively.
Warning
- close As with any other programming language, unbalanced binary trees in Java can become very tall and are ineffective.