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

That is one other fascinating coding downside that’s primarily based on a binary tree and principally requested newbie programmers. When you’ve got some expertise in fixing binary tree-based issues then it is moderately simple to unravel as a result of, like many different binary tree algorithms, you should utilize recursion to print all leaf nodes of a binary tree in Java. Because the tree is a recursive knowledge construction, you may apply the identical algorithm to each the left and proper subtree. To be able to clear up this downside, the very first thing it is best to know is what’s a leaf node as a result of if you do not know that then you definately will not be capable of clear up the issue. Effectively, a leaf node is the one whose left and proper little one nodes are null.

So you may print all leaf nodes by traversing the tree, checking every node to seek out if their left and proper nodes are null, after which printing that node. That might be your leaf node.

The logic could be very a lot much like post-order traversal however as an alternative of simply printing node, you additionally must first test if each left and proper youngsters are null or not. It is usually one of many incessantly requested programming interview questions.

Because the binary tree is a vital a part of Information Constructions and Algorithms, you may anticipate a few questions on binary bushes and binary search bushes, also called BST in your programming job interview, like whether or not a given tree is a binary search tree or not? 

That is why information of important knowledge construction and algorithms is necessary for any programmer be it a Java, Python, or C++ developer. In the event you really feel that you just lack important Information Construction ability or wish to enhance your information about Information Constructions and Algorithms, then I recommend you check out Information Constructions and Algorithms: Deep Dive Utilizing Java, one of many complete course which covers a lot of the important knowledge buildings and algorithms.

Steps to seek out all leaf nodes in a binary tree in Java

Listed below are the steps you may comply with 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 each proper and left tree is null, that is your leaf node
3. repeat the method with each left and proper subtree

And, right here is our Java methodology 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.worth);
    }

    printLeaves(node.left);
    printLeaves(node.proper);

  }

You’ll be able to see that this methodology accepts a TreeNode, which is nothing however our class to characterize a binary tree node. It comprises a price and reference to 2 different nodes, left and proper.

To be able to begin processing, you cross the basis node to this methodology. It then checks if it is null or not, if not then it additional checks if it is a leaf node or not, if sure, then it prints the worth of the node and repeats the method with left and proper subtree.

That is the place recursion is helpful since you name the printLeaves() methodology once more with the left and proper nodes. The logic to test if a node is a leaf or not is straightforward, if each left and proper youngsters of that node are null then it is a leaf node. This logic is encapsulated within the isLeaf() methodology of the TreeNode class.

Btw, should you battle with algorithms and recursion, I want to introduce you to a brand new algorithm e-book referred to as Grokking Algorithms by Aditya Bhargava. I simply purchased a duplicate of this e-book and I’m glad to say it made understanding algorithms fairly simple.

So, if you’re like many programmers who perceive recursion, however do not know the right way to give you a recursive resolution to an issue, then you have to learn this e-book to enhance your understanding.

In the event you favor on-line programs greater than books, which many builders do these days, then you too can take a look at Algorithms and Information Constructions – Half 1 and a couple of programs on Pluralsight.

Btw, you would wish a Pluralsight membership to entry this course, which prices round $29 month-to-month or $299 yearly. I’ve one and I additionally recommend all builders have that plan as a result of Pluralsight is like NetFlix for Software program builders.

It has greater than 5000+ good high quality programs on all the newest subjects. Since we programmers must be taught new issues day by day, an funding of $299 USD shouldn’t be unhealthy.

Btw, it additionally affords a 10-day free trial with none obligation which lets you watch 200 hours of content material. You’ll be able to watch this course at no cost by signing for that trial.

Java Program to print all leaf nodes of a binary tree utilizing recursion

Right here is the entire program, which you’ll be able to run and check. It first creates a binary tree as proven under after which calls the printLeaves() methodology to print all leaf nodes of a binary tree.

This program makes use of recursion due to printLeaves() methodology calls itself to recursively print leaf nodes from the left and proper subtree. 

You’ll be able to additional see Information Constructions in Java: An Interview Refresher course on Educative to be taught extra in regards to the binary tree and different tree algorithms. It is an awesome interactive, text-based course to refresh knowledge construction for coding interviews. I additionally just like the Educative platform for his or her reasonably priced plan of $14.99 per thirty days and 100+ high quality programs for coding interviews and different tech abilities. 

Right here is our binary tree with four-leaf nodes D, E, G, and Okay

And, right 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 
 * utilizing recursion
 * enter :   a
 *          / 
 *         b   f
 *        /   / 
 *       c   e g  h
 *      /           
 *     d            ok 
 * 
 * output: d e g ok 
 */

public class Predominant {

  public static void fundamental(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 ok = new TreeNode("ok");

    TreeNode c = new TreeNode("c", d, null);
    TreeNode h = new TreeNode("h", ok, 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 utilizing recursion
    System.out
        .println("Printing all leaf nodes of binary tree in Java (recursively)");
    printLeaves(root);

  }

  /**
   * A category to characterize a node in binary tree
   */
  non-public static class TreeNode {
    String worth;
    TreeNode left;
    TreeNode proper;

    TreeNode(String worth) {
      this.worth = worth;
    }

    TreeNode(String knowledge, TreeNode left, TreeNode proper) {
      this.worth = knowledge;
      this.left = left;
      this.proper = proper;
    }

    boolean isLeaf() {
      return left == null ? proper == null : false;
    }
  }

  /**
   * Java methodology to print leaf nodes utilizing recursion
   * 
   * @param root
   * 
   */
  public static void printLeaves(TreeNode node) {
    // base case
    if (node == null) {
      return;
    }

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

    printLeaves(node.left);
    printLeaves(node.proper);

  }
}

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

You’ll be able to see that solely leaf nodes are printed by this system. I do know this downside is moderately easy however it may be tough if the interviewer additionally asks you to unravel this downside with out recursion, as mentioned right here.

That is all about the right way to print all leaves of a binary tree in Java utilizing recursion. It is one of the vital frequent binary tree-based issues and it is anticipated from a pc science graduate to unravel this downside.

Since laptop fundamentals and Information, buildings are a vital a part of any programming job interview, I strongly recommend you learn a tried and examined course or books like I’ve shared under to be taught extra about bushes like a binary tree, binary search tree, self-balanced binary bushes like AVL and Pink-black tree.

Additional Studying
Information Constructions and Algorithms: Deep Dive Utilizing Java
Algorithms and Information Constructions – Half 1 and a couple of
Cracking the Coding Interview – 189 Questions and Options
Information Constructions in Java: An Interview Refresher

Associated knowledge construction and algorithms issues in Java

• How you can implement in-order traversal in Java? (resolution)
• 20+ binary tree-based coding issues from Interview’s (questions)
• How you can implement pre-order traversal in Java?  (resolution)
• 7 Finest Programs to be taught Information Construction and Algorithms (programs)
• How you can implement in-order traversal in Java with out recursion? (resolution)
• 10 Free Information Construction and algorithms programs for rookies (programs)
• How you can discover the third factor from the top of a linked checklist in Java? (resolution)
• 21 string-based coding issues from the interview (questions)
• 100+ coding issues and few tricks to crack interview (questions)
• How you can traverse a binary tree in pre-order with out utilizing recursion? (resolution)
• 5 Books to arrange knowledge construction and algorithm for programming/coding interviews (checklist)
• How you can implement a binary search tree in Java? (program)
• How you can discover the center factor of the linked checklist utilizing a single cross? (resolution)
• How you can reverse a singly linked checklist in Java? (resolution)
• How you can implement a linked checklist utilizing generics in Java? (resolution)
• 10 Books to be taught Algorithms for programmers (books)
• How you can print duplicate components of an array in Java? (resolution)

Thanks for studying this text thus far. In the event you like this coding interview query then please share it along with your buddy and colleagues. When you’ve got any doubts or suggestions then please drop a be aware. It’s also possible to comply with me on Twitter (javinpaul).

P. S. – If you’re new to Information Construction and Algorithms world and in search of a free on-line coaching course to kick begin your journey then you too can see this Information Constructions in Java for Newbies free course on Udemy. It is an awesome course for rookies and it is fully free.