Monday, 2 April 2018

How to print all leaf nodes of binary tree in Java?

This is another interesting coding problem which is based on binary tree and like many other binary tree algorithms, you can use recursion to print all leaf nodes of a binary tree in Java. Since the tree is a recursive data structure, you can apply the same algorithm to the left and right subtree. A leaf node is the one whose left and right child nodes are null. So you can print all leaf nodes by traversing the tree, checking if the left and right nodes are null and then printing that leaf node. The logic is very much similar to post order traversal but instead of just printing node, we first check if both left and right children are null or not. It is also one of the frequently asked coding questions. Since the binary tree is an essential part of Data structures and algorithms, you can expect a couple of questions on binary trees and BST e.g. whether a given tree is binary search tree or not? This one is rather simple but it can be tricky if interviewer also asks you to solve this problem without recursion.

Steps to find all leaf nodes in binary tree

Here are the steps you can follow to print all leaf nodes of binary tree:

1. If tree node is null then return
2. print the node if both right and left tree are null, that's your leaf node
3. repeat the process with left and right subtree

and here is the function to implement this logic into code:

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

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

    printLeaves(node.left);
    printLeaves(node.right);

  }

You can see that this method accept a TreeNode, which is nothing but our class to represent a binary tree node. It contains a value and reference to two other nodes, left and right. In order to start processing, you pass root node to this method. It then checks if its null or not, if not then it further checks if it's a leaf node or not, if yes, then its print the value of the node and repeat the process with left and right subtree.

This is where recursion is useful because you call the printLeaves() method again with left and right node. The logic to check if a node is a leaf or not is simple, if both left and right children of that node are null then it's a leaf node. This logic is encapsulated in the isLeaf() method of TreeNode class.

Java Program to print all leaf nodes of binary tree using recursion


Here is the complete program, which you can run and test. It first creates a binary tree as shown in below and then calls the printLeaves() method to print all leaf nodes of a binary tree. This program uses recursion because of printLeaves() method call itself to recursively print leaf nodes from the left and right subtree.

Here is our binary tree with four leaf nodes D, E, G, and K

Oracle Java Tutorials and Materials, Oracle Java Learning, Oracle Java Certifications

and here is our program to print all leaf nodes of this binary tree in Java:

/*
 * 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)");
    printLeaves(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 recursion
   * 
   * @param root
   * 
   */
  public static void printLeaves(TreeNode node) {
    // base case
    if (node == null) {
      return;
    }

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

    printLeaves(node.left);
    printLeaves(node.right);

  }
}

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


That's all about how to print all leaves of a binary tree in Java using recursion. It's one of the most common binary tree based problem and its expected from a computer science graduate to solve this problem. Since computer fundamentals and Data structures are an essential part of any programming job interview.

Related Posts