How To Count Give Away Of Foliage Nodes Inwards A Binary Tree Inwards Coffee - Iterative As Well As Recursive Solution

Hello guys, today I am going to beak close an interesting binary tree based coding occupation from Programming Job interviews. If yous bring attended a couplet of technical interviews thence at that spot is a expert direct chances that yous already bring seen this query close counting a pose out of leafage nodes inwards a binary tree. If yous know how to solve this occupation thence it's good in addition to expert but if yous haven't don't worry, yous volition acquire inwards this article. If yous follow this weblog thence yous mightiness know that I bring 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 yous squall upwardly thence yous tin usage the same algorithm to count a pose out of leafage nodes inwards the binary tree which nosotros bring used inwards the final article, spell printing all leafage nodes of a binary tree inwards 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 inwards a binary tree. They are the nodes which reside inwards the last marker of a binary tree in addition to they don't bring whatever children. In guild to count the full pose out of leafage nodes inwards a binary tree, yous involve to traverse the tree in addition to growth the count variable whenever yous reckon a leafage node.

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

By the way, if yous are non familiar amongst the binary tree information construction itself, then, I propose yous to start acquire through a comprehensive course of written report 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 aid yous a lot inwards solving coding problems

I bring besides been writing posts close roughly essential information construction in addition to algorithms for quite roughly fourth dimension immediately in addition to I intend it's a expert fourth dimension to merely aspect dorsum on what I bring covered thence far in addition to what yous tin hold back inwards future.

As far equally the binary tree is concerned, nosotros bring 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 bring covered next coding problems:

• Linked listing implementation using generics
• Finding the middle chemical component subdivision of linked listing inwards ane pass
• Algorithm to opposite a linked list
• Finding Nth chemical component subdivision from final inwards a linked list

I bring besides covered a lot of topics on the array, which yous tin reckon here in addition to a lot of topics on String algorithm, available here. 

In the future, I am thinking to overstep on amongst to a greater extent than tree algorithms in addition to besides include roughly advanced String searching algorithms similar Rabin-Karp in addition to Knuth-Morris-Pratt Algorithms. If yous non heard of these algorithms before, I propose yous reading Introduction to Algorithms book. One of the classic mass to acquire information construction in addition to algorithms. 

Algorithm to count the pose out of leafage nodes of binary tree using Recursion

The algorithm to count a full pose out of leafage nodes is rattling similar to the before occupation close printing leafage node.

Here are the actual steps to follow:

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

in addition to 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 yous notice this method is private in addition to I bring declared this method within BinaryTree class. In guild to access it outside, I bring created roughly other method countLeafNodesRecursively() as shown below:

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

There are 2 reasons for doing that, the start before method expects a starting node, which should live root. It's cleaner for the customer to merely telephone weep upwardly 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 access it in addition to the actual method is person thence that nobody tin reckon it in addition to the developer tin alter the implementation inwards futurity without affecting clients. This is genuinely a measure blueprint of exposing recursive methods which involve a parameter.

Btw, if yous sympathise recursion but create exercise to write recursive methods to solve real-world problems similar this one, thence yous should bring together a expert course of written report on Algorithms in addition to Data construction like iterative InOrder traversal example, nosotros bring used a Stack to traverse the binary tree. Here are the exact steps of the iterative algorithm to acquire a full pose out of leafage nodes of a binary tree:

1) if the root is goose egg thence furnish zero.
2) start the count amongst zero
3) force the root into Stack
4) loop until Stack is non empty
5) popular the final node in addition to force left in addition to correct children of the final node if they are non null.
6) growth the count

At the destination of the loop, the count contains the full pose out of leafage nodes. Here is the sample code based upon the inwards 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 reckon the logic is quite straightforward. The fourth dimension complexity of this algorithm is O(n) because yous involve to see all nodes of the binary tree to count a full pose out of leafage nodes.

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

You tin farther reckon a expert information construction in addition to algorithm books like Grokking Algorithms by Aditya Bhargava to acquire to a greater extent than close Stack in addition to LIFO information structures. Unlike other books, this explains the concept inwards a much to a greater extent than interesting agency in addition to makes this complex theme flake easier.

Java Program to count the pose out of leafage nodes inwards a binary tree

Here is the consummate program to count a full pose out of leafage nodes inwards a given binary tree inwards Java. This plan 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 at that spot are 4 leafage nodes inwards this tree (d, e, g, in addition to h), your plan should impress 4. The countLeafNodesRecursively() method solves this occupation using recursion and countLeafNodes() solves this occupation 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 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 pose out 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 pose out 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 pose out 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 pose out 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 close how to count the pose out of leafage nodes inwards a binary tree inwards Java. You bring learned to solve this occupation both past times using recursion in addition to iteration. As inwards 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 inwards Java? [solution]

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

How to banking concern stand upwardly for if an array contains a pose out inwards Java? [solution]

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

Write a plan to honor the missing pose out inwards integer array of 1 to 100? [solution]

How exercise yous opposite an array inwards house inwards 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 yous similar this article thence delight percentage amongst your friends in addition to colleagues. If yous bring whatever query or doubtfulness thence delight allow us know in addition to I'll endeavour to honor an reply for you. As ever suggestions, comments, innovative in addition to ameliorate answers are most welcome.

P. S. If yous are thinking what's next, good the original 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 yous solve those without taking aid from the Internet, yous volition live inwards a dissever league of programmers.