How to Find/Print Leaf nodes in a Binary Tree in Java without Recursion - Example

In the last article, you have learned how to print all leaf nodes of a binary tree in Java by using Recursion, a useful technique to solve binary tree problems and in this article, we'll answer the same question without using Recursion. Why should we do this? Well, it's a typical pattern on a programming job interview to solve the same problem using both Recursion and Iteration. Since some questions are easy to solve using recursion like linked list problems, binary tree-based problems, tower of Hanoi, or Fibonacci series but their non-recursive solution is comparatively tricky, the interviewer tests candidates against this shift in the algorithm.

If you have attended your computer science classes and enjoyed it there, then you know that we can use Stack to convert a recursive algorithm to an iterative one. I'll use the same technique to print all leaf nodes of a binary tree without recursion.

Here are steps to solve this problem iteratively:

• Insert the root into a Stack
• Loop through Stack until its empty
• Pop the last node from Stack and push the left and right child of the node into Stack, if they are not null.
• If both left and right children are null then just print the value, that's your leaf node.

and here is the implementation of the above algorithm to print leaf nodes

Seems easy right? Well, once you know the solution, everything looks easy, but until you find the answer, you struggle even on simple steps.

If you are like many developers who understand recursion but don't know how to come up with a recursive solution, then I suggest you join an excellent course like Data Structures and Algorithms: Deep Dive Using Java on Udemy, it's one of the best routes to learn and master data structure and Algorithms.

How to Find and Print all leaf nodes without Recursion in a Binary tree?

Here is the complete Java program to print all leaves of a binary tree without using recursion. This example uses a Stack to store tree nodes during traversal and print the leaf nodes, for which the left and right subtree is null.

The logic used here is similar to pre-order or post-order traversal depending upon whether you first check the left or right subtree.

If you are interested in solving more binary tree-based problems, then please check the Cracking the Coding Interview book. It has the biggest collection of data structure and algorithm problems, including binary tree and binary search tree from tech interviews.

Anyway, here is the binary tree we'll use in this example, you can see that there are four-leaf nodes in this binary tree-like. d, e, g, and k.

Once you run the below program, you will see it prints the leaf nodes as d, e, g, and k. Btw, if you are preparing for a job interview or new in the programming world, I also suggest you join the right course You should also read a good book on Data structure and algorithms like Algorithms and Data Structures - Part 1 and 2 on Pluralsight to learn more about different tree traversal algorithms.

And, If you like books then the Grokking Algorithm by Aditya Bhargava is another good one to understand Recursion and simple data structure.  I was reading it from the last two weekends, and I have thoroughly enjoyed its approach via real-world examples of Algorithms.

Java Program to Print all leaves of a Binary tree without Recursion

import java.util.Stack;

/*
 * Java Program to print all leaf nodes of binary tree 
 * using recursion
 * input : a
 *        / \
 *       b   f
 *      / \ / \
 *     c  e g  h
 *    /         \ 
 *   d           k 
 * 
 * output: d e g k     
 */

public class Main {

  public static void main(String[] args) throws Exception {

    // let's create a binary tree
    TreeNode d = new TreeNode("d");
    TreeNode e = new TreeNode("e");
    TreeNode g = new TreeNode("g");
    TreeNode k = new TreeNode("k");

    TreeNode c = new TreeNode("c", d, null);
    TreeNode h = new TreeNode("h", k, null);

    TreeNode b = new TreeNode("b", c, e);
    TreeNode f = new TreeNode("f", g, h);

    TreeNode root = new TreeNode("a", b, f);

    // print all leaf nodes of binary tree using recursion
    System.out
        .println("Printing all leaf nodes of binary tree in Java
                  (recursively)");
    printLeaf(root);

  }

  /**
   * A class to represent a node in binary tree
   */
  private static class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;

    TreeNode(String value) {
      this.value = value;
    }

    TreeNode(String data, TreeNode left, TreeNode right) {
      this.value = data;
      this.left = left;
      this.right = right;
    }

    boolean isLeaf() {
      return left == null ? right == null : false;
    }
  }

  /**
   * Java method to print leaf nodes using iteration
   * 
   * @param root
   * 
   */
  public static void printLeaf(TreeNode root) {

    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();

      if (node.left != null) {
        stack.add(node.left);
      }

      if (node.right != null) {
        stack.add(node.right);
      }

      if (node.isLeaf()) {
        System.out.printf("%s ", node.value);
      }

    }

  }
}

Output
Printing all leaf nodes of binary tree in Java (recursively)
k g e d  

That's all about how to print all leaf nodes of a binary tree in Java without using recursion. You can use this solution anytime but especially when an interviewer asks to solve this problem using iteration or loop. The order of leaf nodes will depend on whether you first check the left node or right node, just in case of pre-order, and post-order traversal.

Other binary tree and data structure tutorials you may like to explore

• How to implement a binary search tree in Java? (program)
• How to implement in-order traversal in Java? (solution)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• How to implement in-order traversal in Java without recursion? (solution)
• How to implement pre-order traversal in Java?  (solution)
• 10 Algorithms Books Every Programmer Should Read (books)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• How to traverse a binary tree in pre-order without using recursion? (solution)
• How to reverse an array in place in Java? (solution)
• How to print duplicate elements of an array in Java? (solution)
• How to implement a linked list using generics in Java? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to find the middle element of the linked list using a single pass? (solution)
• How to find the 3rd element from the end of a linked list in Java? (solution)
• 5 data structure and algorithm books for coding interviews (list)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this Java Array tutorial, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these Easy to Advanced Data Structures courses on Udemy. It's authored by a Google Software Engineer and Algorithm expert and it's completely free of cost.