How to print the nodes of a binary tree in sorted order
Hello guys, in this shot you will learn how to print all the nodes of a binary tree in sorted order. The in-order traversal is one of the three popular ways to traverse a binary tree data structure, the other two being the pre-order and post-order. During the in-order traversal algorithm, the left subtree is explored first, followed by the root, and finally the nodes in the right subtree.
The basic steps
You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited. The in-order traversal is also known as the left-node-right or left-root-right traversal or the LNR traversal algorithm.
Similar to the pre-order algorithm, it is also a depth-first algorithm because it explores the depth of a binary tree before exploring siblings. Since it is one of the fundamental binary tree algorithms, it’s quite popular in programming interviews.
These traversal algorithms are also the basis for learning more advanced binary tree algorithms; hence, every programmer should learn, understand, and know how to implement them.
The easiest way to implement the in-order traversal algorithm in Java or any programming language is by using recursion. Since the binary tree is a recursive data structure, recursion is the natural choice for solving a tree-based problem. The inOrder() method in the BinaryTree class below implements the logic to traverse a binary tree using recursion.
From an interview point of view, in-order traversal is extremely important because it also prints the nodes of a binary search tree in sorted order, but only if a given tree is a binary search tree. If you remember, in BST, the values of nodes in the left subtree are lower than the root, and the values of nodes in the right subtree are higher than the root. The in-order traversal literally means IN order. I mean, the nodes are printed in sorted order.
Btw, even though these three algorithms (pre-order, in-order, and post-order) are popular binary tree traversal algorithms, they are not the only ones. You also have other breadth-first ways to traverse a binary tree, like level-order traversal.
The recursive algorithm to implement in-order traversal
The recursive algorithm of an in-order traversal is very simple. You just need to call the inOrder() method of BinaryTree class in the order you want to visit the tree. It is extremely important that you include the base case, which is the key to any recursive algorithm.
For example, in this problem, the base case occurs when you reach the leaf node and there are no further nodes to explore. At that point in time, recursion starts to wind down. Here are the exact steps to traverse the binary tree using in-order traversal:
- Visit left node
- Print value of the root
- Visit right node
Here is the basic code to implement this algorithm using recursion in Java:
private void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.printf("%s ", node.data);
inOrder(node.right);
}
There is another inOrder() method, which exposes the private method that actually performs the traversal.
This is the standard way to write a recursive method that takes an input. This makes it easier for a client to call the method.
public void inOrder() {
inOrder(root);
}
In the code below, you can see that we start with the root and then recursively call the inOrder() method with node.left, which means we are going down the left subtree until we hit node == null (our base case).
At this point in time, the inOrder() method will return and execute the next line, which prints node.data. After that, it recursively calls inOrder() with node.right, which will initiate the same process again.
Code
import java.util.Stack;/** Java Program to traverse a binary search tree* using inorder traversal without recursion* and print all nodes in sorted order* In InOrder traversal first left node is visited, followed by root* and right node.** input:* 40* /\* 20 50* / \ \* 10 30 60* / / \* 5 67 78** output: 5 10 20 30 40 50 60 67 78*/public class main {public static void main(String[] args) throws Exception { // construct the binary tree given in questionBinaryTree bt = BinaryTree.create();// traversing binary tree using InOrder traversal using recursionSystem.out.println("printing nodes of binary tree on InOrder using recursion"); bt.inOrder();}}class BinaryTree {static class TreeNode {String data;TreeNode left, right;TreeNode(String value) {this.data = value;left = right = null;}}// root of binary treeTreeNode root;/*** traverse the binary tree in in-order traversal algorithm*/public void inOrder() {inOrder(root);}private void inOrder(TreeNode node) {if (node == null) {return;}inOrder(node.left);System.out.printf("%s ", node.data);inOrder(node.right);}/*** Java method to create binary tree with test data** @return a sample binary tree for testing*/public static BinaryTree create() {BinaryTree tree = new BinaryTree();TreeNode root = new TreeNode("40");tree.root = root;tree.root.left = new TreeNode("20");tree.root.left.left = new TreeNode("10");tree.root.left.left.left = new TreeNode("5");tree.root.left.right = new TreeNode("30");tree.root.right = new TreeNode("50");tree.root.right.right = new TreeNode("60");tree.root.left.right.left = new TreeNode("67");tree.root.left.right.right = new TreeNode("78");return tree;}}
