Hello guys, today I am going to talk about an interesting binary tree-based coding problem from Programming Job interviews. If you have attended a couple of technical interviews then there is a good chance that you already have seen this question about counting the number of leaf nodes in a binary tree. If you know how to solve this problem then it's well and good but if you haven't don't worry, you will learn in this article. If you follow this blog then you might know that I have discussed a lot of data structure and algorithms problems here, including array, linked list, hash table, binary tree, and binary search tree.
If you remember then you can use the same algorithm to count a number of leaf nodes in the binary tree which we have used in the last article, while printing all leaf nodes of a binary tree in Java, using both recursion and iteration.
The logic is the same for the leaf node, any node whose left and right children are null is known as a leaf node in a binary tree. They are the nodes that reside in the last level of a binary tree and they don't have any children. In order to count the total number of leaf nodes in a binary tree, you need to traverse the tree and increase the count variable whenever you see a leaf node.
Since a binary tree is an essential data structure and algorithm topic for programming interviews, it's better to prepare these kinds of questions. I'll show how to solve this using both recursion and iteration in Java in this article.
By the way, if you are not familiar with the binary tree data structure itself, then, I suggest you first go through a comprehensive online course on essential Data Structure and Algorithms to at least get an understanding of basic data structures like an array, linked list, binary tree, hash tables, and binary search tree. That will help you a lot in solving coding problems
I have also been writing posts about some essential data structure and algorithms for quite some time now and I think it's a good time to just look back on what I have covered so far and what you can expect in the future.
As far as the binary tree is concerned, we have covered the following topics:
And, on the linked list topic we have covered the following coding problems:
Here are the actual steps to follow:
1) If the node is null return 0, this is also the base case of our recursive algorithm
2) If a leaf node is encountered then return 1
3) Repeat the process with left and right subtree
4) Return the sum of leaf nodes from both left and right subtree
and here is the sample code based upon the above logic
If you notice this method is private and I have declared this method inside BinaryTree class. In order to access it outside, I have created another method countLeafNodesRecursively() as shown below:
There are two reasons for doing that, the first earlier method expects a starting node, which should be root. It's cleaner for the client to just call this method as root is already available to BinaryTree class. The wrapper method then passes the root to the actual method which counts leaf nodes.
The wrapper method is public so that the client can access it and the actual method is private so that nobody can see it and the developer can change the implementation in the future without affecting clients. This is actually a standard pattern of exposing recursive methods that need a parameter.
Btw, if you understand recursion but struggle to write recursive methods to solve real-world problems like this one, then you should join a good course on Algorithms and Data structure like
If you remember then you can use the same algorithm to count a number of leaf nodes in the binary tree which we have used in the last article, while printing all leaf nodes of a binary tree in Java, using both recursion and iteration.
The logic is the same for the leaf node, any node whose left and right children are null is known as a leaf node in a binary tree. They are the nodes that reside in the last level of a binary tree and they don't have any children. In order to count the total number of leaf nodes in a binary tree, you need to traverse the tree and increase the count variable whenever you see a leaf node.
Since a binary tree is an essential data structure and algorithm topic for programming interviews, it's better to prepare these kinds of questions. I'll show how to solve this using both recursion and iteration in Java in this article.
By the way, if you are not familiar with the binary tree data structure itself, then, I suggest you first go through a comprehensive online course on essential Data Structure and Algorithms to at least get an understanding of basic data structures like an array, linked list, binary tree, hash tables, and binary search tree. That will help you a lot in solving coding problems
I have also been writing posts about some essential data structure and algorithms for quite some time now and I think it's a good time to just look back on what I have covered so far and what you can expect in the future.
As far as the binary tree is concerned, we have covered the following topics:
- Binary search tree implementation
- PreOrder traversal, both iterative and recursive
- PostOrder traversal
- InOrder traversal
- Algorithm to print all leaves of binary tree
And, on the linked list topic we have covered the following coding problems:
- Linked list implementation using generics
- Finding the middle element of the linked list in one pass
- Algorithm to reverse a linked list
- Finding Nth element from last in a linked list
I have also covered a lot of topics on the array, which you can see here, and a lot of topics on the String algorithm, available here.
In the future, I am thinking to continue with more tree algorithms and also including some advanced String searching algorithms like Rabin-Karp and Knuth-Morris-Pratt Algorithms. If you have not heard of these algorithms before, I suggest you read Introduction to Algorithms book. One of the classic books to learn data structure and algorithms.
Algorithm to count the number of leaf nodes of binary tree using Recursion
The algorithm to count the total number of leaf nodes is very similar to the earlier problem about printing a leaf node.Here are the actual steps to follow:
1) If the node is null return 0, this is also the base case of our recursive algorithm
2) If a leaf node is encountered then return 1
3) Repeat the process with left and right subtree
4) Return the sum of leaf nodes from both left and right subtree
and here is the sample code based upon the above logic
private int countLeaves(TreeNode node) { if (node == null) return 0; if (node.isLeaf()) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } }
If you notice this method is private and I have declared this method inside BinaryTree class. In order to access it outside, I have created another method countLeafNodesRecursively() as shown below:
public int countLeafNodesRecursively() { return countLeaves(root); }
There are two reasons for doing that, the first earlier method expects a starting node, which should be root. It's cleaner for the client to just call this method as root is already available to BinaryTree class. The wrapper method then passes the root to the actual method which counts leaf nodes.
The wrapper method is public so that the client can access it and the actual method is private so that nobody can see it and the developer can change the implementation in the future without affecting clients. This is actually a standard pattern of exposing recursive methods that need a parameter.
Btw, if you understand recursion but struggle to write recursive methods to solve real-world problems like this one, then you should join a good course on Algorithms and Data structure like