The right way to Discover/Print Leaf nodes in a Binary Tree in Java with out Recursion – Instance

Within the final article, you could have realized how one can print all leaf nodes of a binary tree in Java by utilizing Recursion, a helpful method to unravel binary tree issues and on this article, we’ll reply the identical query with out utilizing Recursion. Why ought to we do that? Effectively, it is a typical sample on a programming job interview to unravel the identical drawback utilizing each Recursion and Iteration. Since some questions are simple to unravel utilizing recursion like linked checklist issues, binary tree-based issues, tower of Hanoi, or Fibonacci sequence however their non-recursive answer is relatively tough, the interviewer assessments candidates towards this shift within the algorithm.

When you’ve got attended your laptop science lessons and loved it there, then you recognize that we are able to use Stack to transform a recursive algorithm to an iterative one. I will use the identical method to print all leaf nodes of a binary tree with out recursion.

Listed below are steps to unravel this drawback iteratively:

• Insert the foundation right into a Stack
• Loop by means of Stack till its empty
• Pop the final node from Stack and push the left and proper baby of the node into Stack, if they don’t seem to be null.
• If each left and proper youngsters are null then simply print the worth, that is your leaf node.

and right here is the implementation of the above algorithm to print leaf nodes

Appears simple proper? Effectively, as soon as you recognize the answer, every part appears simple, however till you discover the reply, you battle even on easy steps.

If you’re like many builders who perceive recursion however do not know how one can provide you with a recursive answer, then I recommend you be a part of a superb course like Knowledge Constructions and Algorithms: Deep Dive Utilizing Java on Udemy, it is the most effective routes to study and grasp knowledge construction and Algorithms.

The right way to Discover and Print all leaf nodes with out Recursion in a Binary tree?

Right here is the whole Java program to print all leaves of a binary tree with out utilizing recursion. This instance makes use of a Stack to retailer tree nodes throughout traversal and print the leaf nodes, for which the left and proper subtree is null.

The logic used right here is just like pre-order or post-order traversal relying upon whether or not you first test the left or proper subtree.

If you’re serious about fixing extra binary tree-based issues, then please test the Cracking the Coding Interview guide. It has the largest assortment of information construction and algorithm issues, together with binary tree and binary search tree from tech interviews.

Anyway, right here is the binary tree we’ll use on this instance, you may see that there are four-leaf nodes on this binary tree-like. d, e, g, and ok.

When you run the beneath program, you will notice it prints the leaf nodes as d, e, g, and ok. Btw, if you’re getting ready for a job interview or new within the programming world, I additionally recommend you be a part of the suitable course You also needs to learn a great guide on Knowledge construction and algorithms like Algorithms and Knowledge Constructions – Half 1 and 2 on Pluralsight to study extra about completely different tree traversal algorithms.

And, For those who like books then the Grokking Algorithm by Aditya Bhargava is one other good one to grasp Recursion and easy knowledge construction.  I used to be studying it from the final two weekends, and I’ve totally loved its strategy by way of real-world examples of Algorithms.

Java Program to Print all leaves of a Binary tree with out Recursion

import java.util.Stack;

/*
 * Java Program to print all leaf nodes of binary tree 
 * utilizing recursion
 * enter : a
 *        / 
 *       b   f
 *      /  / 
 *     c  e g  h
 *    /          
 *   d           ok 
 * 
 * output: d e g ok     
 */

public class Essential {

  public static void major(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 ok = new TreeNode("ok");

    TreeNode c = new TreeNode("c", d, null);
    TreeNode h = new TreeNode("h", ok, null);

    TreeNode b = new TreeNode("b", c, e);
    TreeNode f = new TreeNode("f", g, h);

    TreeNode root = new TreeNode("a", b, f);

    // print all leaf nodes of binary tree utilizing recursion
    System.out
        .println("Printing all leaf nodes of binary tree in Java
                  (recursively)");
    printLeaf(root);

  }

  /**
   * A category to symbolize a node in binary tree
   */
  non-public static class TreeNode {
    String worth;
    TreeNode left;
    TreeNode proper;

    TreeNode(String worth) {
      this.worth = worth;
    }

    TreeNode(String knowledge, TreeNode left, TreeNode proper) {
      this.worth = knowledge;
      this.left = left;
      this.proper = proper;
    }

    boolean isLeaf() {
      return left == null ? proper == null : false;
    }
  }

  /**
   * Java technique to print leaf nodes utilizing iteration
   * 
   * @param root
   * 
   */
  public static void printLeaf(TreeNode root) {

    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    whereas (!stack.isEmpty()) {
      TreeNode node = stack.pop();

      if (node.left != null) {
        stack.add(node.left);
      }

      if (node.proper != null) {
        stack.add(node.proper);
      }

      if (node.isLeaf()) {
        System.out.printf("%s ", node.worth);
      }

    }

  }
}

Output
Printing all leaf nodes of binary tree in Java (recursively)
ok g e d  

That is all about how one can print all leaf nodes of a binary tree in Java with out utilizing recursion. You should use this answer anytime however particularly when an interviewer asks to unravel this drawback utilizing iteration or loop. The order of leaf nodes will rely upon whether or not you first test the left node or proper node, simply in case of pre-order and post-order traversal.

Different binary tree and knowledge construction tutorials it’s possible you’ll wish to discover

Thanks for studying this text up to now. For those who like this Java Array tutorial, then please share it with your pals and colleagues. When you’ve got any questions or suggestions, then please drop a remark.

P. S. – If you’re searching for some Free Algorithms programs to enhance your understanding of Knowledge Construction and Algorithms, you then also needs to test these Simple to Superior Knowledge Constructions programs on Udemy. It is authored by a Google Software program Engineer and Algorithm professional and it is utterly freed from price.