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.
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
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 kYou 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.
Source: Java67
The Tech Platform
Comentarios