How to Print all leaf Nodes of a Binary tree in Java - Coding Interview Questions

This is another interesting coding problem which is based on a binary tree and mostly asked beginner programmers. If you have some experience in solving binary tree based problems then it's rather easy to solve because, 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 both the left and right subtree. In order to solve this problem, the first thing you should know is what is a leaf node because if you don't know that then you won't be able to solve the problem. Well, a leaf node is the one who's left and right child nodes are null.

So you can print all leaf nodes by traversing the tree, checking each node to find if their left and right nodes are null and then printing that node. That would be your leaf node.

The logic is very much similar to post order traversal but instead of just printing node, you also need to first check if both left and right children are null or not. It is also one of the frequently asked programming interview 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 binary search tree, also known as BST in your programming job interview, like whether a given tree is a binary search tree or not? 

That's why a good knowledge of essential data structure and algorithms are mandatory for any programmer be it a Java, Python or C++ developer. If you feel that you lack essential Data Structure skill or want to improve your knowledge about Data Structures and Algorithms, then I suggest you take a look at Data Structures and Algorithms: Deep Dive Using Java, one of the comprehensive course which covers most of the essential data structures and algorithms.



Steps to find all leaf nodes in a binary tree

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

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

And, here is our Java method 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 the 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 the 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.

If you prefer online courses more than books, which many developers do nowadays, then you can also checkout Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight.

How to Print all leaf Nodes of a Binary tree in Java - Coding Interview Questions


Btw, you would need a Pluralsight membership to access this course, which costs around $29 monthly or $299 annually. I have one and I also suggest all developers have that plan because Pluralsight is like NetFlix for Software developers.

It has more than 5000+ good quality courses on all latest topics. Since we programmers have to learn new things every day, an investment of $299 USD is not bad.

Btw, it also offers a 10-day free trial without any obligation which allows you to watch 200 hours of content. You can watch this course for free by signing for that trial.



Java Program to print all leaf nodes of a 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 Data Structures and Algorithms: Deep Dive Using Java 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

You can see that only leaf nodes are printed by the program. I know this problem is rather simple but it can be tricky if interviewer also asks you to solve this problem without recursion, as discussed here.


Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions


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 courses or books like 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 a binary search tree in Java? (program)
  • How to find the 3rd element from the end of a linked list in Java? (solution)
  • How to find the middle element of the linked list using a single pass? (solution)
  • How to reverse a singly linked list in Java? (solution)
  • How to implement a linked list using generics in Java? (solution)
  • How to print duplicate elements of an array in Java? (solution)

Thanks for reading this article so far. If you like this coding interview question then please share with your friend and colleagues. If you have any doubt or feedback then please drop a note. You can also follow me on Twitter (javinpaul).

No comments:

Post a Comment