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:

1. Visit left node
2. Print value of the root
3. 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