In this post, we will see
how to count leaf nodes in a binary tree in Java. Understanding how to count leaf nodes is useful for various applications in computer science, such as calculating the depth or height of a tree, optimizing search operations, and more. It is also a common interview question to practice questions on binary trees.
2. What are Leaf Nodes?
Leaf nodes are the nodes which don’t have any children. These are also terminal nodes and denote the end of the tree structure.
3. Implementation
There are two ways to count leaf nodes in a binary tree:
4.1 Recursive Solution
The recursive solution is very straightforward. Here are the steps for counting the number of leaf nodes:
Code for recursion will be:
|
|
// Recursive Solution /* To get the count of leaf nodes in a binary tree */ public static int getLeafCountOfBinaryTree(TreeNode node) { if(node == null) return 0; if(node.left == null && node.right == null) return 1; else return getLeafCountOfBinaryTree(node.left) + getLeafCountOfBinaryTree(node.right); } |
The time complexity for the recursive approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited to determine whether it is a leaf node or not.
The space complexity is O(w) where w is the maximum width in the binary tree. This is because the maximum number of nodes in the stack is proportional to the width of the binary tree at any point in time.
4.2 Iterative Solution
For recursion, we use an implicit stack. So here, to convert the recursive solution to iterative, we will use an explicit stack.
Steps for the iterative solution:
- Create an empty
stack and push the root node to it.
- Initialize a variable
count to track the number of leaf nodes.
- Do the following when the
stack is not empty:
- Pop a node from the
stack and check if it is a leaf node. If yes, increase the count.
- Push the
right child of the popped node to the stack.
- Push the
left child of the popped node to the stack.
We are pushing the right child first, so it will be processed after the left subtree as the Stack is LIFO (Last In, First Out).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int countLeavesIterative(TreeNode root) { if (root == null) return 0; Stack<TreeNode> stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode current = stack.pop(); if (current.left == null && current.right == null) { count++; } if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } return count; } |
The time complexity for iterative approach is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited to determine whether it is a leaf node or not.
The space complexity is O(w) where w is the maximum width in the binary tree. This is because the maximum number of nodes in the stack is proportional to the width of the binary tree at any point in time.
5. Complete Java Program
Let’s say our binary tree is:
Here is complete java program for counting number of leaf nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
package org.arpit.java2blog.generic; import java.util.Stack; public class BinaryTreeLeafCount { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } } // Recursive Solution /* To get the count of leaf nodes in a binary tree*/ public static int getLeafCountOfBinaryTree(TreeNode node) { if(node == null) return 0; if(node.left ==null && node.right==null) return 1; else return getLeafCountOfBinaryTree(node.left)+ getLeafCountOfBinaryTree(node.right); } // Iterative solution public static int getLeafCountOfBinaryTreeIterative(TreeNode root) { if (root == null) return 0; Stack<TreeNode> stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode current = stack.pop(); if (current.left == null && current.right == null) { count++; } if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } return count; } public static void main(String[] args) { // Creating a binary tree TreeNode rootNode=createBinaryTree(); System.out.println("Number of leaf nodes in binary tree(Recursive) :"+getLeafCountOfBinaryTree(rootNode)); System.out.println("Number of leaf nodes in binary tree(Iterative) :"+getLeafCountOfBinaryTreeIterative(rootNode)); } public static TreeNode createBinaryTree() { TreeNode rootNode =new TreeNode(40); TreeNode node20=new TreeNode(20); TreeNode node10=new TreeNode(10); TreeNode node30=new TreeNode(30); TreeNode node60=new TreeNode(60); TreeNode node50=new TreeNode(50); TreeNode node70=new TreeNode(70); rootNode.left=node20; rootNode.right=node60; node20.left=node10; node20.right=node30; node60.left=node50; node60.right=node70; return rootNode; } } |
Run above program and you will get following output:
|
|
Number of leaf nodes in binary tree(Recursive) :4 Number of leaf nodes in binary tree(Iterative) :4 |
6. Conclusion
In this article, we covered about how to count leaf nodes in Binary tree. We have discussed two approaches: Iterative and Recursive. We also discussed about time and space complexity for the same.
Please go through Frequently asked java interview programs for more such programs.
