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, as discussed here.

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.

Btw, if you struggle with algorithms and recursion, I would like to introduce you to a new algorithm book called Grokking Algorithms by Aditya Bhargava. I just bought a copy of this book and I am happy to say it made understanding algorithms quite easy.  So, if you are like many programmers who understand recursion, but don't know how to come up with a recursive solution to a problem, then you must read this book to improve your understanding.

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



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. See Introduction to Algorithms to learn more about the binary tree and other tree algorithms.

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

How to print all leaf nodes of binary tree in Java
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, I strongly suggest you read a tried and tested book e.g. Introduction to Algorithms to learn more about trees e.g. binary tree, binary search tree, self-balanced binary trees like AVL and Red-black tree.

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

References
Binary tree data structure


No comments:

Post a Comment