Hello guys, today I am going to utter almost an interesting binary tree based coding work from Programming Job interviews. If y'all convey attended a dyad of technical interviews too then in that place is a skillful adventure that y'all already convey seen this query almost counting a unwrap of leafage nodes inwards a binary tree. If y'all know how to solve this work too then it's good too skillful but if y'all haven't don't worry, y'all volition larn inwards this article. If y'all follow this weblog too then y'all mightiness know that I convey discussed a lot of data construction too algorithms problems here, including array, linked list, hash table, binary tree, too binary search tree.
If y'all recall too then y'all tin give notice utilisation the same algorithm to count a unwrap of leafage nodes inwards the binary tree which nosotros convey used inwards the concluding article, piece printing all leafage nodes of a binary tree inwards Java, using both recursion too iteration.
The logic is the same for the leafage node, whatever node whose left too correct children are null is known every bit a leafage node inwards a binary tree. They are the nodes which reside inwards the last marking of a binary tree too they don't convey whatever children. In club to count the full unwrap of leafage nodes inwards a binary tree, y'all ask to traverse the tree too increase the count variable whenever y'all reckon a leafage node.
Since a binary tree is an essential information construction too algorithm topics for programming interviews, it's meliorate to laid upwards these kinds of questions. I'll demo how to solve this using both recursion too iteration inwards Java inwards this article.
By the way, if y'all are non familiar amongst the binary tree information construction itself, then, I propose y'all to commencement become through a comprehensive class on essential Data Structure too Algorithms like Data Structures too Algorithms: Deep Dive Using Java on Udemy to at to the lowest degree acquire an agreement of basic information structures similar array, linked list, binary tree, hash tables, too binary search tree. That volition assistance y'all a lot inwards solving coding problems
I convey likewise been writing posts almost but about essential information construction too algorithms for quite but about fourth dimension instantly too I intend it's a skillful fourth dimension to but facial expression dorsum on what I convey covered thence far too what y'all tin give notice await inwards future.
As far every bit the binary tree is concerned, nosotros convey covered the next topics:
And, on linked listing topic nosotros convey covered next coding problems:
Here are the actual steps to follow:
1) If the node is zilch provide 0, this is likewise the base of operations instance of our recursive algorithm
2) If a leafage node is encountered too then provide 1
3) Repeat the procedure amongst left too correct subtree
4) Return the total of leafage nodes from both left too correct subtree
too hither is the sample code based upon inwards a higher house logic
If y'all notice this method is private too I convey declared this method within BinaryTree class. In club to access it outside, I convey created but about other method countLeafNodesRecursively() as shown below:
There are 2 reasons for doing that, the commencement before method expects a starting node, which should live root. It's cleaner for the customer to but telephone weep upwards this method every bit root is already available to BinaryTree class. The wrapper method too then passes the root to the actual method which counts leafage nodes.
The wrapper method is public thence that the customer tin give notice access it too the actual method is someone thence that nobody tin give notice reckon it too the developer tin give notice alter the implementation inwards hereafter without affecting clients. This is genuinely a measure blueprint of exposing recursive methods which ask a parameter.
Btw, if y'all empathize recursion but care to write recursive methods to solve real-world problems similar this one, too then y'all should bring together a skillful class on Algorithms too Data construction like iterative InOrder traversal example, nosotros convey used a Stack to traverse the binary tree. Here are the exact steps of the iterative algorithm to acquire a full unwrap of leafage nodes of a binary tree:
1) if the root is zilch too then provide zero.
2) start the count amongst zero
3) force the root into Stack
4) loop until Stack is non empty
5) popular the concluding node too force left too correct children of the concluding node if they are non null.
6) increase the count
At the cease of the loop, the count contains the full unwrap of leafage nodes. Here is the sample code based upon the inwards a higher house logic too algorithm:
You tin give notice reckon the logic is quite straightforward. The fourth dimension complexity of this algorithm is O(n) because y'all ask to see all nodes of the binary tree to count a full unwrap of leafage nodes.
The Stack is a LIFO information construction too nosotros convey used the JDK implementation java.util.Stack which likewise extends the Vector class.
You tin give notice farther reckon a skillful information construction too algorithm books like Grokking Algorithms by Aditya Bhargava to larn to a greater extent than almost Stack too LIFO information structures. Unlike other books, this explains the concept inwards a much to a greater extent than interesting agency too makes this complex topic flake easier.
Since in that place are iv leafage nodes inwards this tree (d, e, g, too h), your plan should impress 4. The countLeafNodesRecursively() method solves this work using recursion and countLeafNodes() solves this work without recursion.
The working of methods is explained inwards the previous paragraph.
That's all almost how to count the unwrap of leafage nodes inwards a binary tree inwards Java. You convey learned to solve this work both yesteryear using recursion too iteration. As inwards most cases, the recursive algorithm is easier to write, read too empathize that the iterative algorithm, but, even the iterative algorithm is non every bit tough every bit the iterative quicksort or iterative post-order traversal algorithm.
Further Learning
Data Structures too Algorithms: Deep Dive Using Java
courses]TOp thirty linked listing coding problems from Interviews (questions) How to take duplicates from an array inwards Java? [solution] 30+ Array-based Coding Problems from Interviews (questions) How to cheque if an array contains a unwrap inwards Java? [solution] Free Data Structure too Algorithms Courses for Programmers (courses) Write a plan to detect the missing unwrap inwards integer array of 1 to 100? [solution] How exercise y'all contrary an array inwards house inwards Java? [solution] 50+ Data Structure too Algorithms Coding Problems from Interviews (questions) 10 Algorithms Books Every Programmer should read [books] 10 Algorithms courses to Crack Coding Interviews [courses]
If y'all recall too then y'all tin give notice utilisation the same algorithm to count a unwrap of leafage nodes inwards the binary tree which nosotros convey used inwards the concluding article, piece printing all leafage nodes of a binary tree inwards Java, using both recursion too iteration.
The logic is the same for the leafage node, whatever node whose left too correct children are null is known every bit a leafage node inwards a binary tree. They are the nodes which reside inwards the last marking of a binary tree too they don't convey whatever children. In club to count the full unwrap of leafage nodes inwards a binary tree, y'all ask to traverse the tree too increase the count variable whenever y'all reckon a leafage node.
Since a binary tree is an essential information construction too algorithm topics for programming interviews, it's meliorate to laid upwards these kinds of questions. I'll demo how to solve this using both recursion too iteration inwards Java inwards this article.
By the way, if y'all are non familiar amongst the binary tree information construction itself, then, I propose y'all to commencement become through a comprehensive class on essential Data Structure too Algorithms like Data Structures too Algorithms: Deep Dive Using Java on Udemy to at to the lowest degree acquire an agreement of basic information structures similar array, linked list, binary tree, hash tables, too binary search tree. That volition assistance y'all a lot inwards solving coding problems
I convey likewise been writing posts almost but about essential information construction too algorithms for quite but about fourth dimension instantly too I intend it's a skillful fourth dimension to but facial expression dorsum on what I convey covered thence far too what y'all tin give notice await inwards future.
As far every bit the binary tree is concerned, nosotros convey covered the next topics:
- Binary search tree implementation
- PreOrder traversal, both iterative too recursive
- PostOrder traversal
- InOrder traversal
- Algorithm to impress all leaves of binary tree
And, on linked listing topic nosotros convey covered next coding problems:
- Linked listing implementation using generics
- Finding the middle chemical ingredient of linked listing inwards 1 pass
- Algorithm to contrary a linked list
- Finding Nth chemical ingredient from concluding inwards a linked list
I convey likewise covered a lot of topics on the array, which y'all tin give notice reckon here too a lot of topics on String algorithm, available here.
In the future, I am thinking to hand off amongst to a greater extent than tree algorithms too likewise include but about advanced String searching algorithms similar Rabin-Karp too Knuth-Morris-Pratt Algorithms. If y'all non heard of these algorithms before, I propose y'all reading Introduction to Algorithms book. One of the classic mass to larn information construction too algorithms.
Algorithm to count the unwrap of leafage nodes of binary tree using Recursion
The algorithm to count a full unwrap of leafage nodes is rattling similar to the before work almost printing leafage node.Here are the actual steps to follow:
1) If the node is zilch provide 0, this is likewise the base of operations instance of our recursive algorithm
2) If a leafage node is encountered too then provide 1
3) Repeat the procedure amongst left too correct subtree
4) Return the total of leafage nodes from both left too correct subtree
too hither is the sample code based upon inwards a higher house 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 y'all notice this method is private too I convey declared this method within BinaryTree class. In club to access it outside, I convey created but about other method countLeafNodesRecursively() as shown below:
public int countLeafNodesRecursively() { return countLeaves(root); }
There are 2 reasons for doing that, the commencement before method expects a starting node, which should live root. It's cleaner for the customer to but telephone weep upwards this method every bit root is already available to BinaryTree class. The wrapper method too then passes the root to the actual method which counts leafage nodes.
The wrapper method is public thence that the customer tin give notice access it too the actual method is someone thence that nobody tin give notice reckon it too the developer tin give notice alter the implementation inwards hereafter without affecting clients. This is genuinely a measure blueprint of exposing recursive methods which ask a parameter.
Btw, if y'all empathize recursion but care to write recursive methods to solve real-world problems similar this one, too then y'all should bring together a skillful class on Algorithms too Data construction like iterative InOrder traversal example, nosotros convey used a Stack to traverse the binary tree. Here are the exact steps of the iterative algorithm to acquire a full unwrap of leafage nodes of a binary tree:
1) if the root is zilch too then provide zero.
2) start the count amongst zero
3) force the root into Stack
4) loop until Stack is non empty
5) popular the concluding node too force left too correct children of the concluding node if they are non null.
6) increase the count
At the cease of the loop, the count contains the full unwrap of leafage nodes. Here is the sample code based upon the inwards a higher house logic too algorithm:
public int countLeafNodes() { if (root == null) { return 0; } Stack stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); if (node.isLeaf()) count++; } return count; } }
You tin give notice reckon the logic is quite straightforward. The fourth dimension complexity of this algorithm is O(n) because y'all ask to see all nodes of the binary tree to count a full unwrap of leafage nodes.
The Stack is a LIFO information construction too nosotros convey used the JDK implementation java.util.Stack which likewise extends the Vector class.
You tin give notice farther reckon a skillful information construction too algorithm books like Grokking Algorithms by Aditya Bhargava to larn to a greater extent than almost Stack too LIFO information structures. Unlike other books, this explains the concept inwards a much to a greater extent than interesting agency too makes this complex topic flake easier.
Java Program to count the unwrap of leafage nodes inwards a binary tree
Here is the consummate program to count a full unwrap of leafage nodes inwards a given binary tree inwards Java. This plan demonstrates both recursive too iterative algorithm to solve this problem. In this program, we'll utilisation the next binary tree for testing purpose.Since in that place are iv leafage nodes inwards this tree (d, e, g, too h), your plan should impress 4. The countLeafNodesRecursively() method solves this work using recursion and countLeafNodes() solves this work without recursion.
The working of methods is explained inwards the previous paragraph.
import java.util.Stack; /* * Java Program to count all leafage nodes of binary tree * amongst too without recursion. * input : a * / \ * b f * / \ / \ * c e g h * / \ * d k * * output: 4 */ public class Main { public static void main(String[] args) throws Exception { // let's create a binary tree BinaryTree bt = new BinaryTree(); bt.root = new BinaryTree.TreeNode("a"); bt.root.left = new BinaryTree.TreeNode("b"); bt.root.right = new BinaryTree.TreeNode("f"); bt.root.left.left = new BinaryTree.TreeNode("c"); bt.root.left.right = new BinaryTree.TreeNode("e"); bt.root.left.left.left = new BinaryTree.TreeNode("d"); bt.root.right.left = new BinaryTree.TreeNode("g"); bt.root.right.right = new BinaryTree.TreeNode("h"); bt.root.right.right.right = new BinaryTree.TreeNode("k"); // count all leafage nodes of binary tree using recursion System.out .println("total unwrap of leafage nodes of binary tree inwards Java (recursively)"); System.out.println(bt.countLeafNodesRecursively()); // count all leafage nodes of binary tree without recursion System.out .println("count of leafage nodes of binary tree inwards Java (iteration)"); System.out.println(bt.countLeafNodes()); } } class BinaryTree { static class TreeNode { String value; TreeNode left, right; TreeNode(String value) { this.value = value; left = right = null; } boolean isLeaf() { return left == null ? right == null : false; } } // root of binary tree TreeNode root; /** * Java method to calculate unwrap of leafage node inwards binary tree. * * @param node * @return count of leafage nodes. */ public int countLeafNodesRecursively() { return countLeaves(root); } private int countLeaves(TreeNode node) { if (node == null) return 0; if (node.isLeaf()) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } } /** * Java method to count leafage nodes using iteration * * @param root * @return unwrap of leafage nodes * */ public int countLeafNodes() { if (root == null) { return 0; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); int count = 0; while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); if (node.isLeaf()) count++; } return count; } } Output full unwrap of leafage nodes of a binary tree in Java (recursively) 4 count of leafage nodes of a binary tree in Java (iteration) 4
That's all almost how to count the unwrap of leafage nodes inwards a binary tree inwards Java. You convey learned to solve this work both yesteryear using recursion too iteration. As inwards most cases, the recursive algorithm is easier to write, read too empathize that the iterative algorithm, but, even the iterative algorithm is non every bit tough every bit the iterative quicksort or iterative post-order traversal algorithm.
Further Learning
Data Structures too Algorithms: Deep Dive Using Java
courses]
Thanks for reading this article thence far. If y'all similar this article too then delight portion amongst your friends too colleagues. If y'all convey whatever query or dubiety too then delight allow us know too I'll assay to detect an reply for you. As ever suggestions, comments, innovative too meliorate answers are most welcome.
P. S. If y'all are thinking what's next, good the master copy challenge for whatever serious programmer is to solve information construction too algorithm problems given in Algorithm Design Manual by Steven S. Skiena. If y'all solve those without taking assistance from the Internet, y'all volition live inwards a dissever league of programmers.