How to print leaf nodes of binary tree without recursion

In the last article, you have learned how to print all leaf nodes of a binary tree in Java by using recursion and in this article, we'll solve the same problem without using recursion. Why should we do this? Well, it's a common pattern on programming job interview to solve the same problem using recursion and iteration. Since some problems are easy to solve using recursion e.g. tree based problems, tower of Hanoi, or Fibonacci series but their non-recursive solution is comparatively difficult, interviewer test candidates against this shift in the algorithm. If you have attended your computer science classes and enjoyed 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 Stack
  • Loop through Stack until its empty
  • Pop the last node from Stack and push 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 above algorithm to print leaf nodes

Seems easy right? Well, once you know the solution everything looks easy but until you find the solution you struggle even on common steps. If you are like many developer who understand recursion but don't know how to come up with a recursive solution, then I suggest you to read Grokking Algorithm by Aditya Bhargava. I was reading it from last two weekends and I have thoroughly enjoyed it's approach via real world examples of Algorithms.



Java Program to print all leaf nodes without recursion in 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 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 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 problem 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 i.e. 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.


Java Program to print all leaves of 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 whether you first check left node or right node, just in case of pre-order and post-order traversal. You should also read a good book on Data structure and algorithm e.g. Introduction to Algorithms to learn more about different tree traversal algorithms.


Other binary tree and data structure tutorials you may like to explore
  • How to implement binary search tree in Java? (program)
  • How to implement in-order traversal in Java? (solution)
  • How to implement in-order traversal in Java without recursion? (solution)
  • How to implement pre-order traversal in Java?  (solution)
  • 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 linked list using generic in Java? (solution)
  • How to reverse a singly linked list in Java? (solution)
  • How to find the middle element of linked list using single pass? (solution)
  • How to find the 3rd element from the end of linked list in Java? (solution)
  • 5 data structure and algorithm books for coding interviews (list)



No comments:

Post a Comment