Given a Binary Tree, the task is to print the leaf nodes from left to right. The nodes must be printed in the order they appear from left to right.
Examples:
Input :
1
/ \
2 3
/ \ / \
4 5 6 7
Output :4 5 6 7
Input :
4
/ \
5 9
/ \ / \
8 3 7 2
/ / \
12 6 1
Output :12 3 7 6 1
We have already discussed the Recursive approach. Here we will solve the problem using two stacks.
Approach:The idea is to use two stacks, one to store all the nodes of the tree and the other one to store all the leaf nodes. We will pop the top node of the first stack. If the node has a left child, we will push it on top of the first stack, if it has a right child then we will push it onto the top of the first stack, but if the node is a leaf node then we will push it onto the top of the second stack. We will do it for all the nodes until we have traversed the Binary tree completely.
Then we will start popping the second stack and print all its elements until the stack gets empty.
Below is the implementation of the above approach:
C++
// C++ program to print all the leaf nodes// of a Binary tree from left to right#include <bits/stdc++.h>using namespace std;// Binary tree nodestruct Node { Node* left; Node* right; int data;};// Function to create a new// Binary nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}// Function to Print all the leaf nodes// of Binary tree using two stacksvoid PrintLeafLeftToRight(Node* root){ // Stack to store all the nodes of tree stack<Node*> s1; // Stack to store all the leaf nodes stack<Node*> s2; // Push the root node s1.push(root); while (!s1.empty()) { Node* curr = s1.top(); s1.pop(); // If current node has a left child // push it onto the first stack if (curr->left) s1.push(curr->left); // If current node has a right child // push it onto the first stack if (curr->right) s1.push(curr->right); // If current node is a leaf node // push it onto the second stack else if (!curr->left && !curr->right) s2.push(curr); } // Print all the leaf nodes while (!s2.empty()) { cout << s2.top()->data << " "; s2.pop(); }}// Driver codeint main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->right = newNode(7); root->left->left->left = newNode(10); root->left->left->right = newNode(11); root->right->right->left = newNode(8); PrintLeafLeftToRight(root); return 0;} |
Java
// Java program to print all the leaf nodes// of a Binary tree from left to rightimport java.util.*;class GFG {// Binary tree nodestatic class Node{ Node left; Node right; int data;};// Function to create a new// Binary nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp;}// Function to Print all the leaf nodes// of Binary tree using two stacksstatic void PrintLeafLeftToRight(Node root){ // Stack to store all the nodes of tree Stack<Node> s1 = new Stack<>(); // Stack to store all the leaf nodes Stack<Node> s2 = new Stack<>();; // Push the root node s1.push(root); while (!s1.empty()) { Node curr = s1.peek(); s1.pop(); // If current node has a left child // push it onto the first stack if (curr.left!=null) s1.push(curr.left); // If current node has a right child // push it onto the first stack if (curr.right!=null) s1.push(curr.right); // If current node is a leaf node // push it onto the second stack else if (curr.left==null && curr.right==null) s2.push(curr); } // Print all the leaf nodes while (!s2.empty()) { System.out.print(s2.peek().data +" "); s2.pop(); }}// Driver codepublic static void main(String[] args){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(7); root.left.left.left = newNode(10); root.left.left.right = newNode(11); root.right.right.left = newNode(8); PrintLeafLeftToRight(root);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to print all the leaf # nodes of a Binary tree from left to right # Binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to Print all the leaf nodes # of Binary tree using two stacks def PrintLeafLeftToRight(root): # Stack to store all the nodes # of tree s1 = [] # Stack to store all the # leaf nodes s2 = [] # Push the root node s1.append(root) while len(s1) != 0: curr = s1.pop() # If current node has a left child # push it onto the first stack if curr.left: s1.append(curr.left) # If current node has a right child # push it onto the first stack if curr.right: s1.append(curr.right) # If current node is a leaf node # push it onto the second stack elif not curr.left and not curr.right: s2.append(curr) # Print all the leaf nodes while len(s2) != 0: print(s2.pop().data, end = " ") # Driver code if __name__ == "__main__": root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.right = Node(7) root.left.left.left = Node(10) root.left.left.right = Node(11) root.right.right.left = Node(8) PrintLeafLeftToRight(root) # This code is contributed# by Rituraj Jain |
C#
// C# program to print all the leaf nodes// of a Binary tree from left to rightusing System;using System.Collections.Generic; class GFG {// Binary tree nodepublic class Node{ public Node left; public Node right; public int data;};// Function to create a new// Binary nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp;}// Function to Print all the leaf nodes// of Binary tree using two stacksstatic void PrintLeafLeftToRight(Node root){ // Stack to store all the nodes of tree Stack<Node> s1 = new Stack<Node>(); // Stack to store all the leaf nodes Stack<Node> s2 = new Stack<Node>();; // Push the root node s1.Push(root); while (s1.Count != 0) { Node curr = s1.Peek(); s1.Pop(); // If current node has a left child // push it onto the first stack if (curr.left != null) s1.Push(curr.left); // If current node has a right child // push it onto the first stack if (curr.right != null) s1.Push(curr.right); // If current node is a leaf node // push it onto the second stack else if (curr.left == null && curr.right == null) s2.Push(curr); } // Print all the leaf nodes while (s2.Count != 0) { Console.Write(s2.Peek().data + " "); s2.Pop(); }}// Driver codepublic static void Main(String[] args){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(7); root.left.left.left = newNode(10); root.left.left.right = newNode(11); root.right.right.left = newNode(8); PrintLeafLeftToRight(root);}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach // Binary tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create a new // Binary node function newNode(data) { let temp = new Node(data); return temp; } // Function to Print all the leaf nodes // of Binary tree using two stacks function PrintLeafLeftToRight(root) { // Stack to store all the nodes of tree let s1 = []; // Stack to store all the leaf nodes let s2 = []; // Push the root node s1.push(root); while (s1.length > 0) { let curr = s1[s1.length - 1]; s1.pop(); // If current node has a left child // push it onto the first stack if (curr.left!=null) s1.push(curr.left); // If current node has a right child // push it onto the first stack if (curr.right!=null) s1.push(curr.right); // If current node is a leaf node // push it onto the second stack else if (curr.left==null && curr.right==null) s2.push(curr); } // Print all the leaf nodes while (s2.length > 0) { document.write(s2[s2.length - 1].data +" "); s2.pop(); } } let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(7); root.left.left.left = newNode(10); root.left.left.right = newNode(11); root.right.right.left = newNode(8); PrintLeafLeftToRight(root); </script> |
Output:
10 11 5 8
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
