Tuesday, April 11, 2023

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

This is another interesting coding problem that 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 whose 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 trees, 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 is 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 in Java

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 accepts 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 it's null or not, if not then it further checks if it's a leaf node or not, if yes, then it prints the value of the node and repeats the process with left and right subtree.


This is where recursion is useful because you call the printLeaves() method again with the left and right nodes. 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 check out 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





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 below and then calls the printLeaves() method to print all leaf nodes of a binary tree.

This program uses recursion because of printLeaves() method calls itself to recursively print leaf nodes from the left and right subtree. 

You can further see Data Structures in Java: An Interview Refresher course on Educative to learn more about the binary tree and other tree algorithms. It's a great interactive, text-based course to refresh data structure for coding interviews. I also like the Educative platform for their affordable plan of $14.99 per month and 100+ quality courses for coding interviews and other tech skills. 

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 the interviewer also asks you to solve this problem without recursion, as discussed here.

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 problems and it's 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 course or books like I have shared below to learn more about trees like a 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)
  • 20+ binary tree-based coding problems from Interview's (questions)
  • How to implement pre-order traversal in Java?  (solution)
  • 7 Best Courses to learn Data Structure and Algorithms (courses)
  • How to implement in-order traversal in Java without recursion? (solution)
  • 10 Free Data Structure and algorithms courses for beginners (courses)
  • How to find the 3rd element from the end of a linked list in Java? (solution)
  • 21 string-based coding problems from the interview (questions)
  • 100+ coding problems and few tips to crack interview (questions)
  • 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 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)
  • 10 Books to learn Algorithms for programmers (books)
  • 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 it with your friend and colleagues. If you have any doubts or feedback then please drop a note. You can also follow me on Twitter (javinpaul).

P. S. - If you are new to Data Structure and Algorithms world and looking for a free online training course to kick start your journey then you can also see this Data Structures in Java for Beginners free course on Udemy. It's a great course for beginners and it's completely free.

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.