How to impress leafage nodes of binary tree without recursion

In the last article, you lot accept learned how to impress all leafage nodes of a binary tree inwards Java past times using recursion too inwards this article, we'll solve the same work without using recursion. Why should nosotros produce this? Well, it's a mutual blueprint on programming undertaking interview to solve the same work using recursion too iteration. Since merely about problems are slow to solve using recursion e.g. tree based problems, tower of Hanoi, or Fibonacci series but their non-recursive solution is comparatively difficult, interviewer attempt candidates against this shift inwards the algorithm. If you lot accept attended your estimator scientific discipline classes too enjoyed there, too thus you lot know that nosotros tin flame purpose Stack to convert a recursive algorithm to an iterative one. I'll purpose the same technique to print all leafage nodes of a binary tree without recursion.

Here are steps to solve this work iteratively:

Insert the rootage into Stack
Loop through Stack until its empty
Pop the terminal node from Stack too force left too correct kid of the node into Stack, if they are non null.
If both left too correct children are null too thus merely impress the value, that's your leafage node.

too hither is the implementation of to a higher house algorithm to impress leafage nodes

Seems slow right? Well, in ane lawsuit you lot know the solution everything looks slow but until you lot detect the solution you lot create out fifty-fifty on mutual steps. If you lot are similar many developer who sympathise recursion but don't know how to come upwardly up amongst a recursive solution, too thus I propose you lot to read Grokking Algorithm past times Aditya Bhargava. I was reading it from terminal 2 weekends too I accept thoroughly enjoyed it's approach via existent basis examples of Algorithms.

Java Program to impress all leafage nodes without recursion inwards binary tree

Here is the consummate Java plan to impress all leaves of a binary tree without using recursion. this representative uses a Stack to shop tree nodes during traversal too impress the leafage nodes, for which left too correct subtree is null. The logic used hither is similar to pre-order or post-order traversal depending upon whether you lot outset cheque left or correct subtree.

If you lot are interested inwards solving to a greater extent than binary tree based problems too thus delight cheque the Cracking the Coding Interview book. It has the biggest collection of information construction too algorithm work including binary tree too binary search tree from tech interviews.

Anyway, hither is the binary tree we'll purpose inwards this example, you lot tin flame run across that at that topographic point are 4 leafage nodes inwards this binary tree i.e. d, e, g, too k.

Once you lot run the below program, you lot volition run across it prints the leafage nodes every bit d, e, g, too k.

Java Program to impress all leaves of binary tree without recursion

import java.util.Stack;  /*  * Java Program to impress all leafage nodes of binary tree   * using recursion  * input : a  *        / \  *       b   f  *      / \ / \  *     c  e g  h  *    /         \   *   d           k   *   * output: d e g k       */  public class Main {    public static void main(String[] args) throws Exception {      // let's create a binary tree     TreeNode d = new TreeNode("d");     TreeNode e = new TreeNode("e");     TreeNode g = new TreeNode("g");     TreeNode k = new TreeNode("k");      TreeNode c = new TreeNode("c", d, null);     TreeNode h = new TreeNode("h", k, null);      TreeNode b = new TreeNode("b", c, e);     TreeNode f = new TreeNode("f", g, h);      TreeNode rootage = new TreeNode("a", b, f);      // impress all leafage nodes of binary tree using recursion     System.out         .println("Printing all leafage nodes of binary tree inwards Java (recursively)");     printLeaf(root);    }    /**    * Influenza A virus subtype H5N1 shape to stand upwardly for a node inwards binary tree    */   private static class TreeNode {     String value;     TreeNode left;     TreeNode right;      TreeNode(String value) {       this.value = value;     }      TreeNode(String data, TreeNode left, TreeNode right) {       this.value = data;       this.left = left;       this.right = right;     }      boolean isLeaf() {       return left == null ? right == null : false;     }   }    /**    * Java method to impress leafage nodes using iteration    *     * @param rootage    *     */   public static void printLeaf(TreeNode root) {      if (root == null) {       return;     }     Stack<TreeNode> stack = new Stack<>();     stack.push(root);      while (!stack.isEmpty()) {       TreeNode node = stack.pop();        if (node.left != null) {         stack.add(node.left);       }        if (node.right != null) {         stack.add(node.right);       }        if (node.isLeaf()) {         System.out.printf("%s ", node.value);       }      }    } }  Output Printing all leafage nodes of binary tree in Java (recursively) k g e d

That's all close how to impress all leafage nodes of a binary tree inwards Java without using recursion. You tin flame purpose this solution anytime but peculiarly when an interviewer asks to solve this work using iteration or loop. The gild of leafage nodes volition depend whether you lot outset cheque left node or correct node, merely inwards representative of pre-order too post-order traversal. You should too read a skilful mass on Data construction too algorithm e.g. Introduction to Algorithms to acquire to a greater extent than close dissimilar tree traversal algorithms.

Other binary tree too information construction tutorials you lot may similar to explore

How to implement binary search tree inwards Java? (program)
How to implement in-order traversal inwards Java? (solution)
How to implement in-order traversal inwards Java without recursion? (solution)
How to implement pre-order traversal inwards Java? (solution)
How to traverse a binary tree inwards pre-order without using recursion? (solution)
How to opposite an array inwards house inwards Java? (solution)
How to impress duplicate elements of an array inwards Java? (solution)
How to implement linked listing using generic inwards Java? (solution)
How to opposite a singly linked listing inwards Java? (solution)
How to detect the middle chemical ingredient of linked listing using unmarried pass? (solution)
How to detect the tertiary chemical ingredient from the terminate of linked listing inwards Java? (solution)
5 information construction too algorithm books for coding interviews (list)