How To Impress All Foliage Nodes Of Binary Tree Inwards Coffee - Recursion As Well As Stack

Binary tree based questions are real mutual inward Java or whatsoever other Programming chore interviews. One of the oftentimes asked binary tree questions is "write a computer program to impress all leafage nodes of a binary tree". In social club to solve this problem, yous must know what is a leafage node? H5N1 leafage node inward a binary tree is a node whose left too correct kid is null. They are genuinely the concluding nodes of whatsoever binary tree. In a typical programming interview, yous would hold out given a binary tree too asked to write a computer program to impress all leafage nodes. Usually, all binary tree related questions tin hold out solved easily using recursion because a tree is a recursive information structure, but yous should likewise know how to solve them without recursion.

In general, equally a reckoner scientific discipline graduate yous should know how to convert a recursive algorithm to iterative ane i.e. the ane which uses a loop. One technique is to usage a recursive information construction similar Stack to shop nodes piece yous are traversing through the tree, similar to what nosotros conduct maintain used inward implementing in social club traversal without recursion. I conduct maintain used the same technique inward the minute purpose of this computer program to impress all leafage nodes of a binary tree inward Java using Stack.

The interviewer volition often inquire yous to write both recursive too iterative solution of printing all leafage nodes. If yous know ane but doesn't know other, it volition highlight your limitation, that's why it's of import for candidates to cook both solutions. It volition likewise assistance yous to sympathise both occupation too solution meliorate too prepare the comparative feel required to select betwixt dissimilar solutions inward the existent world.

Btw, If yous are preparing for programming interviews of tech giants similar Amazon, or Google, I advise yous conduct maintain a await at Algorithm Design Manual yesteryear Steven Skiena, that volition assistance yous to prepare a solution for novel algorithmic problems based on your cognition of information structures too algorithms.

Print all leafage nodes of binary tree using Recursion

As I told, it's pretty slowly to solve binary tree based occupation using recursion because yous tin apply the same algorithm to the left tree too correct tree too thus combine the result. In social club to impress the leafage nodes of binary tree, we'll usage the next algorithm:

1) If given node is zip thus return
2) If both left too correct nodes are null, it agency its leafage node, thus impress its value.
3) Recursively see the left too correct subtree.

This logic is same is recursive inward social club traversal (see Introduction to Algorithms), but instead of simply printing the node value later on left too correct subtree traversals, nosotros likewise banking venture fit to encounter if the electrical flow node is a leafage node or non nd thus impress the node value. If both left too correct kid of a node are zip thus it's a leaf node.

Here is the code to impress all leafage nodes of binary tree recursively:

public static void printLeafNodes(TreeNode node) {     // base of operations case     if (node == null) {       return;     }      if (node.left == null && node.right == null) {       System.out.printf("%d ", node.value);     }      printLeafNodes(node.left);     printLeafNodes(node.right);   }

You tin encounter that nosotros are printing the value of leafage too thus calling the same method ane time to a greater extent than for left too correct subtree to impress all leafs recursively. The node == null check serves equally the base of operations instance to halt traversal, a fundamental chemical factor of a recursive algorithm. If yous don't conduct maintain a base of operations instance thus your computer program volition never terminate too eventually expire amongst StackOverFlowError.

Btw, a binary tree is non simply a theoretical concept, it does be inward the existent the world equally well, a adept illustration is next tree which is binary too yous tin encounter that leafage nodes are those which are at the top.

Printing leafage nodes of binary tree using Iteration

If yous cope to solve the occupation (print all leafage nodes) successfully using recursion thus the interviewer volition most probable inquire yous to solve the occupation without recursion i.e. to come upwardly up amongst an iterative solution. You tin usage Stack to impress all leafage nodes of a binary tree. The Stack is a LIFO information construction which is unremarkably used to convert a recursive algorithm to an iterative one.

Here are the steps to impress leafage nodes of binary tree without recursion
1) Create a Stack too force the beginning node
2) loop until Stack is non empty
3) Call Stack.pop() to acquire the concluding chemical factor too shop its left too correct kid if they are non null
4) if both left too correct kid of the concluding node is zip thus it's a leafage node, impress its value

hither is the sample code to impress all leafage nodes of a binary tree using iterative algorithm:

public static void printLeafNodesIteratively(TreeNode root) {      if (root == null) {       return;     }     Stack<TreeNode> stack = new Stack<>();     stack.push(root);      while (!stack.isEmpty()) {       TreeNode node = stack.pop();        if (node.right != null) {         stack.add(node.right);       }        if (node.left != null) {         stack.add(node.left);       }        if (node.left == null && node.right == null) {         System.out.printf("%d ", node.value);       }      }    }

I am using System.out.printf() to impress values of leafage nodes inward the same line. The %d is a formatting teaching to impress int values. The cognition of Stack information construction is mandatory to come upwardly up amongst this solution, this ane time to a greater extent than shows that adept cognition of information construction is essential for coming upwardly amongst meliorate solutions. You should read a adept mass on information construction too algorithm e.g. Algorithms fourth Edition yesteryear Robert Sedgewick to larn to a greater extent than close tree algorithms e.g. tree traversal too others.

Java Program to impress all leafage nodes of binary tree

Here is our sample computer program to impress all leafage nodes of a binary tree inward Java. It demonstrates both iterative too recursive solution of this problem. There are ii methods, printLeafNodes(TreeNode node) to impress leafage nodes using recursion too printLeafNodesIteratively(TreeNode root) to impress leafage nodes without recursion yesteryear using Stack. The TreeNode is a nested static class to correspond a node inward a binary tree. It has iii members, int value, too left too correct TreeNode equally a child. All members conduct maintain bundle bird access to brand testing easier too algorithm to a greater extent than readable. I prefer node.left over node.getLeftChild().

import java.util.Stack;  /*  * Java Program to impress all leafage nodes of given binary tree.  * This computer program demonstrates both recursive too iterative solution  * of this problem.  *   * input :   l  *         /   \  *       25     65  *      /  \   /  \  *     10  34  43  78  *   * output: 10 34 43 78   */  public class Main {    public static void main(String[] args) throws Exception {      // let's do a binary tree     TreeNode n10 = new TreeNode(10);     TreeNode n34 = new TreeNode(34);     TreeNode n43 = new TreeNode(43);     TreeNode n78 = new TreeNode(78);      TreeNode n25 = new TreeNode(25, n10, n34);     TreeNode n65 = new TreeNode(65, n43, n78);     TreeNode beginning = new TreeNode(50, n25, n65);      // impress all leafage nodes of binary tree using recursion     System.out         .println("Printing all leafage nodes of a binary tree inward Java (recursively)");     printLeafNodes(root);      // insert a novel line     System.out.println();      // printing all leafage nodes without recursion inward binary tree     System.out         .println("Printing all leafage nodes of binary tree inward Java using stack");     printLeafNodesIteratively(root);    }    /**    * H5N1 degree to correspond a node inward binary tree    */   private static class TreeNode {     int value;     TreeNode left;     TreeNode right;      TreeNode(int data) {       this.value = data;     }      TreeNode(int data, TreeNode left, TreeNode right) {       this.value = data;       this.left = left;       this.right = right;     }    }    /**    * Java method to impress leafage nodes using recursion    *     * @param beginning    *     */   public static void printLeafNodes(TreeNode node) {     // base of operations case     if (node == null) {       return;     }      if (node.left == null && node.right == null) {       System.out.printf("%d ", node.value);     }      printLeafNodes(node.left);     printLeafNodes(node.right);   }    /**    * Java method to impress leafage nodes using iteration    *     * @param beginning    *     */   public static void printLeafNodesIteratively(TreeNode root) {      if (root == null) {       return;     }     Stack<TreeNode> stack = new Stack<>();     stack.push(root);      while (!stack.isEmpty()) {       TreeNode node = stack.pop();        if (node.right != null) {         stack.add(node.right);       }        if (node.left != null) {         stack.add(node.left);       }        if (node.left == null && node.right == null) {         System.out.printf("%d ", node.value);       }      }    } }   Output Printing all leafage nodes of binary tree in Java (recursively) 10 34 43 78  Printing all leafage nodes of binary tree in Java using stack 10 34 43 78 

That's all close how to impress leafage nodes of a binary tree inward Java. You conduct maintain learned both recursive too iterative algorithm to solve this problem. The recursive algorithm was easier to sympathise too should hold out your default solution, but yous should know how yous tin usage Stack to convert a recursive algorithm to an iterative one.

If the interviewer asks yous to print leafage nodes of a binary tree without recursion, yous should usage the minute solution which uses piece loop too Stack. You tin likewise read a adept mass on information construction too algorithm problems e.g. The Cracking the Coding Interview to practices to a greater extent than binary tree information construction too diverse tree algorithms e.g. preorder, inorder, or postorder traversal based coding problems.

Further Learning
Data Structures too Algorithms: Deep Dive Using Java
solution)

How to implement inward social club traversal inward Java? (solution)

How to traverse a binary tree inward pre-order without using recursion? (solution)

How to implement in-order traversal inward Java without recursion? (solution)

How to notice the third chemical factor from the terminate of linked listing inward Java? (solution)

How to implement linked listing using generic inward Java? (solution)

How to notice the length of singly linked listing inward Java? (solution)

How to opposite a singly linked listing inward Java? (solution)

How to notice the middle chemical factor of linked listing using unmarried pass? (solution)

5 Books to cook information construction too algorithm for programming/coding interviews (list)

Share this post