How to Print all Leaf Nodes of Binary tree in Java - Recursion and Stack Examples

Binary tree based questions is very common in Java or any other programming job interviews. One of the frequently asked binary tree questions is "write a program to print all leaf nodes of a binary tree". In order to solve this problem, you must know what is a leaf node? A leaf node in a binary tree is a node whose left and right child is null. They are actually the last nodes of any binary tree. In a typical programming interview, you would be given a binary tree and asked to write a program to print all leaf nodes. Usually, all binary tree related questions can be solved easily using recursion because a tree is a recursive data structure, but you should also know how to solve them without recursion.

In general, as a computer science graduate, you should know how to convert a recursive algorithm to an iterative one i.e. the one which uses a loop. One technique is to use a recursive data structure like Stack to store nodes while you are traversing through the tree, similar to what we have used in implementing in order traversal without recursion. I have used the same technique in the second part of this program to print all leaf nodes of a binary tree in Java using Stack.

The interviewer will often ask you to write both recursive and iterative solutions of printing all leaf nodes. If you know one but doesn't know others, it will highlight your limitation, that's why it's important for candidates to prepare both solutions. It will also help you to understand both problems and solutions better and develop the comparative sense required to choose between different solutions in the real world.

Btw, If you are preparing for programming interviews with tech giants like Amazon, or Google, I suggest you take a look at these Java data structure courses that will help you to develop a solution for new algorithmic problems based on your knowledge of data structures and algorithms.

Print all leaf nodes of binary tree using Recursion

As I told, it's pretty easy to solve binary tree based problem using recursion because you can apply the same algorithm to the left tree and right tree and then combine the result. In order to print the leaf nodes of a binary tree, we'll use the following algorithm:

1) If the given node is null then return
2) If both left and right nodes are null, it means its leaf node, so print its value.
3) Recursively visit the left and right subtree.

This logic is the same is recursive in order traversal (see Introduction to Algorithms), but instead of just printing the node value after left and right subtree traversals, we also check to see if the current node is a leaf node or not nd then print the node value. If both left and right child of a node are null then it's a leaf node.

Here is the code to print all leaf nodes of binary tree recursively:

public static void printLeafNodes(TreeNode node) {
    // base case
    if (node == null) {
      return;
    }

    if (node.left == null && node.right == null) {
      System.out.printf("%d ", node.value);
    }

    printLeafNodes(node.left);
    printLeafNodes(node.right);
  }

You can see that we are printing the value of leaf and then calling the same method again for left and right subtree to print all leafs recursively. The node == null check serves as the base case to stop traversal, a key element of a recursive algorithm. If you don't have a base case then your program will never terminate and eventually die with StackOverFlowError.

Btw, a binary tree is not just a theoretical concept, it does exist in the real world as well, a good example is the following tree which is binary and you can see those leaf nodes are those which are at the top.

Printing leaf nodes of binary tree using Iteration

If you manage to solve the problem (print all leaf nodes) successfully using recursion then the interviewer will most likely ask you to solve the problem without recursion i.e. to come up with an iterative solution. You can use Stack to print all leaf nodes of a binary tree. The Stack is a LIFO data structure which is usually used to convert a recursive algorithm to an iterative one.

Here are the steps to print leaf nodes of binary tree without recursion
1) Create a Stack and push the root node
2) loop until Stack is not empty
3) Call Stack.pop() to get the last element and store its left and right child if they are not null
4) if both left and right child of the last node is null then it's a leaf node, print its value

here is the sample code to print all leaf nodes of a binary tree using an iterative algorithm:

public static void printLeafNodesIteratively(TreeNode root) {

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

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

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

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

      if (node.left == null && node.right == null) {
        System.out.printf("%d ", node.value);
      }

    }

  }

I am using System.out.printf() to print values of leaf nodes in the same line. The %d is a formatting instruction to print int values. The knowledge of Stack data structure is mandatory to come up with this solution, this again shows that good knowledge of data structure is essential for coming up with better solutions. You should read a good book on data structure and algorithms like Algorithms 4th Edition by Robert Sedgewick to learn more about tree algorithms e.g. tree traversal and others.

Java Program to print all leaf nodes of binary tree

Here is our sample program to print all leaf nodes of a binary tree in Java. It demonstrates both iterative and recursive solutions of this problem. There are two methods, printLeafNodes(TreeNode node) to print leaf nodes using recursion and printLeafNodesIteratively(TreeNode root) to print leaf nodes without recursion by using Stack. 

The TreeNode is a nested static class to represent a node in a binary tree. It has three members, int value, and left and right TreeNode as a child. All members have package level access to make testing easier and the algorithm more readable. I prefer node.left over node.getLeftChild().

import java.util.Stack;

/*
 * Java Program to print all leaf nodes of given binary tree.
 * This program demonstrates both recursive and iterative solution
 * of this problem.
 * 
 * input :   50
 *         /   \
 *       25     65
 *      /  \   /  \
 *     10  34  43  78
 * 
 * output: 10 34 43 78 
 */

public class Main {

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

    // let's create a binary tree
    TreeNode n10 = new TreeNode(10);
    TreeNode n34 = new TreeNode(34);
    TreeNode n43 = new TreeNode(43);
    TreeNode n78 = new TreeNode(78);

    TreeNode n25 = new TreeNode(25, n10, n34);
    TreeNode n65 = new TreeNode(65, n43, n78);
    TreeNode root = new TreeNode(50, n25, n65);

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

    // insert a new line
    System.out.println();

    // printing all leaf nodes without recursion in binary tree
    System.out
        .println("Printing all leaf nodes of binary tree in Java using stack");
    printLeafNodesIteratively(root);

  }

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

    TreeNode(int data) {
      this.value = data;
    }

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

  }

  /**
   * Java method to print leaf nodes using recursion
   * 
   * @param root
   * 
   */
  public static void printLeafNodes(TreeNode node) {
    // base case
    if (node == null) {
      return;
    }

    if (node.left == null && node.right == null) {
      System.out.printf("%d ", node.value);
    }

    printLeafNodes(node.left);
    printLeafNodes(node.right);
  }

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

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

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

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

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

      if (node.left == null && node.right == null) {
        System.out.printf("%d ", node.value);
      }

    }

  }
}


Output
Printing all leaf nodes of binary tree in Java (recursively)
10 34 43 78 
Printing all leaf nodes of binary tree in Java using stack
10 34 43 78 

That's all about how to print leaf nodes of a binary tree in Java. You have learned both recursive and iterative algorithms to solve this problem. The recursive algorithm was easier to understand and should be your default solution, but you should know how you can use Stack to convert a recursive algorithm to an iterative one.

If the interviewer asks you to print leaf nodes of a binary tree without recursion, you should use the second solution which uses while loop and Stack. You can also read a good book on data structure and algorithm problems like The Cracking the Coding Interview book to practices more binary tree data structure and various tree algorithms e.g. preorder, in order, or postorder traversal-based coding problems.


Other data structure and binary tree tutorials you may like

• How to implement pre-order traversal in Java?  (solution)
• How to implement in-order traversal in Java? (solution)
• How to traverse a binary tree in pre-order without using recursion? (solution)
• How to implement in-order traversal in Java without recursion? (solution)
• How to find the 3rd element from the end of the linked list in Java? (solution)
• How to implement a linked lists using generic in Java? (solution)
• How to find the length of a singly linked list in Java? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to find the middle element of a linked list using a single pass? (solution)
• 5 Books to prepare data structure and algorithm for programming/coding interviews (list)