How To Count Publish Of Leafage Nodes Inwards A Binary Tree Inwards Coffee - Iterative Together With Recursive Solution

Hello guys, today I am going to utter most an interesting binary tree based coding occupation from Programming Job interviews. If you lot convey attended a distich of technical interviews thence in that place is a adept jeopardy that you lot already convey seen this enquiry most counting a publish of leafage nodes inward a binary tree. If you lot know how to solve this occupation thence it's good in addition to adept but if you lot haven't don't worry, you lot volition larn inward this article. If you lot follow this weblog thence you lot powerfulness know that I convey discussed a lot of data construction in addition to algorithms problems here, including array, linked list, hash table, binary tree, in addition to binary search tree. 

If you lot recollect thence you lot tin give notice usage the same algorithm to count a publish of leafage nodes inward the binary tree which nosotros convey used inward the concluding article, spell printing all leafage nodes of a binary tree inward Java, using both recursion in addition to iteration.

The logic is the same for the leafage node, whatever node whose left in addition to correct children are null is known equally a leafage node inward a binary tree. They are the nodes which reside inward the last degree of a binary tree in addition to they don't convey whatever children. In gild to count the full publish of leafage nodes inward a binary tree, you lot ask to traverse the tree in addition to increase the count variable whenever you lot reckon a leafage node.

Since a binary tree is an essential information construction in addition to algorithm topics for programming interviews, it's improve to ready these kinds of questions. I'll exhibit how to solve this using both recursion in addition to iteration inward Java inward this article.

By the way, if you lot are non familiar amongst the binary tree information construction itself, then, I advise you lot to commencement acquire through a comprehensive course of pedagogy on essential Data Structure in addition to Algorithms like Data Structures in addition to 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, in addition to binary search tree. That volition assistance you lot a lot inward solving coding problems

I convey too been writing posts most around essential information construction in addition to algorithms for quite around fourth dimension instantly in addition to I intend it's a adept fourth dimension to but facial expression dorsum on what I convey covered thence far in addition to what you lot tin give notice facial expression inward future.

As far equally the binary tree is concerned, nosotros convey covered the next topics:

• Binary search tree implementation
• PreOrder traversal, both iterative in addition to recursive
• PostOrder traversal
• InOrder traversal
• Algorithm to impress all leaves of binary tree

And, on linked listing theme nosotros convey covered next coding problems:

• Linked listing implementation using generics
• Finding the middle chemical factor of linked listing inward i pass
• Algorithm to contrary a linked list
• Finding Nth chemical factor from concluding inward a linked list

I convey too covered a lot of topics on the array, which you lot tin give notice reckon here in addition to a lot of topics on String algorithm, available here. 

In the future, I am thinking to maintain amongst to a greater extent than tree algorithms in addition to too include around advanced String searching algorithms similar Rabin-Karp in addition to Knuth-Morris-Pratt Algorithms. If you lot non heard of these algorithms before, I advise you lot reading Introduction to Algorithms book. One of the classic majority to larn information construction in addition to algorithms. 

Algorithm to count the publish of leafage nodes of binary tree using Recursion

The algorithm to count a full publish of leafage nodes is really similar to the before occupation most printing leafage node.

Here are the actual steps to follow:

1) If the node is nil supply 0, this is too the base of operations instance of our recursive algorithm
2) If a leafage node is encountered thence supply 1
3) Repeat the procedure amongst left in addition to correct subtree
4) Return the total of leafage nodes from both left in addition to correct subtree

in addition to hither is the sample code based upon to 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 you lot notice this method is private in addition to I convey declared this method within BinaryTree class. In gild to access it outside, I convey created around other method countLeafNodesRecursively() as shown below:

 public int countLeafNodesRecursively() {     return countLeaves(root);   }

There are ii 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 telephone this method equally root is already available to BinaryTree class. The wrapper method thence 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 in addition to the actual method is someone thence that nobody tin give notice reckon it in addition to the developer tin give notice modify the implementation inward hereafter without affecting clients. This is genuinely a criterion blueprint of exposing recursive methods which ask a parameter.

Btw, if you lot sympathise recursion but combat to write recursive methods to solve real-world problems similar this one, thence you lot should bring together a adept course of pedagogy on Algorithms in addition to 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 publish of leafage nodes of a binary tree:

1) if the root is nil thence supply 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 in addition to force left in addition to correct children of the concluding node if they are non null.
6) increase the count

At the terminate of the loop, the count contains the full publish of leafage nodes. Here is the sample code based upon the to a higher house logic in addition to 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 you lot ask to see all nodes of the binary tree to count a full publish of leafage nodes.

The Stack is a LIFO information construction in addition to nosotros convey used the JDK implementation java.util.Stack which too extends the Vector class.

You tin give notice farther reckon a adept information construction in addition to algorithm books like Grokking Algorithms by Aditya Bhargava to larn to a greater extent than most Stack in addition to LIFO information structures. Unlike other books, this explains the concept inward a much to a greater extent than interesting means in addition to makes this complex theme flake easier.

Java Program to count the publish of leafage nodes inward a binary tree

Here is the consummate program to count a full publish of leafage nodes inward a given binary tree inward Java. This programme demonstrates both recursive in addition to iterative algorithm to solve this problem. In this program, we'll usage the next binary tree for testing purpose.

Since in that place are 4 leafage nodes inward this tree (d, e, g, in addition to h), your programme should impress 4. The countLeafNodesRecursively() method solves this occupation using recursion and countLeafNodes() solves this occupation without recursion.

The working of methods is explained inward the previous paragraph.

import java.util.Stack;  /*  * Java Program to count all leafage nodes of binary tree   * amongst in addition to 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 publish of leafage nodes of binary tree inward 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 inward 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 publish of leafage node inward 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 publish 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 publish 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 most how to count the publish of leafage nodes inward a binary tree inward Java. You convey learned to solve this occupation both yesteryear using recursion in addition to iteration. As inward most cases, the recursive algorithm is easier to write, read in addition to sympathise that the iterative algorithm, but, even the iterative algorithm is non equally tough equally the iterative quicksort or iterative post-order traversal algorithm.


Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
courses]

TOp xxx linked listing coding problems from Interviews (questions)

How to take duplicates from an array inward Java? [solution]

30+ Array-based Coding Problems from Interviews (questions)

How to cheque if an array contains a publish inward Java? [solution]

Free Data Structure in addition to Algorithms Courses for Programmers (courses)

Write a programme to discovery the missing publish inward integer array of 1 to 100? [solution]

How practice you lot contrary an array inward house inward Java? [solution]

50+ Data Structure in addition to Algorithms Coding Problems from Interviews (questions)

10 Algorithms Books Every Programmer should read [books]

10 Algorithms courses to Crack Coding Interviews [courses]

Thanks for reading this article thence far. If you lot similar this article thence delight part amongst your friends in addition to colleagues. If you lot convey whatever enquiry or incertitude thence delight allow us know in addition to I'll effort to discovery an respond for you. As e'er suggestions, comments, innovative in addition to improve answers are most welcome.

P. S. If you lot are thinking what's next, good the master copy challenge for whatever serious programmer is to solve information construction in addition to algorithm problems given in Algorithm Design Manual by Steven S. Skiena. If you lot solve those without taking assistance from the Internet, you lot volition live inward a carve upward league of programmers.