# Print all leaf nodes of a binary tree using stack

Display all leaf node in binary tree, We can solve this problem in a two way, First are recursion by using (inorder, preorder) tree traversal technique. And second is iterative solution by using stack or other data structure.

Leaf node of a binary tree not contain any left and right subtree. See this example.

Here given code implementation process.

``````/*
C Program
Print all leaf nodes of a binary tree
By using of stack
*/
#include <stdio.h>

#include <stdlib.h>

//structure of Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
struct MyStack
{
struct Node *element;
struct MyStack *next;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
//Create a MyStack element and return this reference
struct MyStack *push(struct Node *tree_node, struct MyStack *top)
{
struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (node != NULL)
{
//set pointer values
node->element = tree_node;
node->next = top;
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
return node;
}
//Remove a top node of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *remove = *top;*top = remove->next;
remove->element = NULL;
remove->next = NULL;
//free the allocated memory of node
free(remove);
remove = NULL;
}
}
//print leaf nodes of binary tree
void print_leaf_node(struct Node *root)
{
if (root != NULL)
{
//Make few MyStack pointer
struct MyStack *top = NULL, *head = NULL;
struct Node *temp = root;
while (top != NULL || temp != NULL)
{
if (temp != NULL)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp->left == NULL && temp->right == NULL)
{
//When get a leaf node
printf("%d ", temp->data);
}
//add tree node into stack
top = push(temp, top);
//visit left subtree
temp = temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = top->element;
//remove stack element
pop( & top);
//visit right-subtree
temp = temp->right;
}
}
}
else
{
}
}
int main()
{
struct Node *root = NULL;
/*Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//Insertion of binary tree nodes
root = insert(17);
root->left = insert(11);
root->right = insert(21);
root->right->right = insert(9);
root->right->left = insert(10);
root->left->left = insert(1);
root->left->right = insert(39);
root->left->right->left = insert(40);
root->right->right->right = insert(2);
printf("Leaf node is : ");
//Display Tree elements
print_leaf_node(root);
return 0;
}``````

#### Output

``Leaf node is : 1 40 10 2``
``````/*
Java Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//Define a Stack Class
class MyStack
{
public Node element;
public MyStack next;
public MyStack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
private MyStack top;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print leaf nodes of binary tree
public void print_leaf_node()
{
if (this.root != null)
{
Node temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp.left == null && temp.right == null)
{
System.out.print(" " + temp.data + " ");
}
//add tree node into MyStack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = this.top.element;
//remove MyStack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
}
}
//remove top element of stack
public void push(Node node)
{
MyStack new_node = new MyStack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
public void pop()
{
if (top != null)
{
MyStack remove = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
System.out.print("Leaf node is : ");
//Display Tree elements
obj.print_leaf_node();
}
}``````

#### Output

``Leaf node is :  1  40  10  2``
``````/*
C++ Program
Print all leaf nodes of a binary tree
By Using Stack
*/
#include <iostream>

using namespace std;
//Binary Tree node
class Node
{
public: int data;
Node * left, * right;
//make a tree node
Node(int data)
{
//Assign field values
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//Define a Stack Class
class MyStack
{
public: Node * element;
MyStack * next;
MyStack(Node * element)
{
this->element = element;
this->next = NULL;
}
};
class BinaryTree
{
public: Node * root;
MyStack * top;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
this->top = NULL;
}
//print leaf nodes of binary tree
void print_leaf_node()
{
if (this->root != NULL)
{
Node * temp = this->root;
while (this->top != NULL || temp != NULL)
{
if (temp != NULL)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp->left == NULL && temp->right == NULL)
{
cout << " " << temp->data << " ";
}
//add tree node into MyStack
this->push(temp);
//visit left subtree
temp = temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = this->top->element;
//remove MyStack element
this->pop();
//visit right-subtree
temp = temp->right;
}
}
}
else
{
cout << "Empty Linked List\n";
}
}
//remove top element of stack
void push(Node * node)
{
MyStack * new_node = new MyStack(node);
new_node->next = this->top;
this->top = new_node;
}
//remove top element of the stack
void pop()
{
if (this->top != NULL)
{
MyStack * remove = this->top;
this->top = this->top->next;
remove->next = NULL;
remove->element = NULL;
remove = NULL;
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree obj = BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root->left = new Node(11);
obj.root->right = new Node(21);
obj.root->right->right = new Node(9);
obj.root->right->right->right = new Node(2);
obj.root->right->left = new Node(10);
obj.root->left->left = new Node(1);
obj.root->left->right = new Node(39);
obj.root->left->right->left = new Node(40);
cout << "Leaf node is : ";
//Display Tree elements
obj.print_leaf_node();
return 0;
}``````

#### Output

``Leaf node is :  1  40  10  2``
``````/*
C# Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Include namespace system
using System;
//Binary Tree node
class Node
{
public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//Define a Stack Class
class MyStack
{
public Node element;
public MyStack next;
public MyStack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
private MyStack top;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print leaf nodes of binary tree
public void print_leaf_node()
{
if (this.root != null)
{
Node temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp.left == null && temp.right == null)
{
Console.Write(" " + temp.data + " ");
}
//add tree node into MyStack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = this.top.element;
//remove MyStack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
}
}
//remove top element of stack
public void push(Node node)
{
MyStack new_node = new MyStack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
public void pop()
{
if (top != null)
{
MyStack remove = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
Console.Write("Leaf node is : ");
//Display Tree elements
obj.print_leaf_node();
}
}``````

#### Output

``Leaf node is :  1  40  10  2``
``````<?php
/*
Php Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
public \$data;
public \$left;
public \$right;
//make a tree node
function __construct(\$data)
{
//Assign field values
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
//Define a Stack Class
class MyStack
{
public \$element;
public \$next;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
}
}
class BinaryTree
{
public \$root;
public \$top;

function __construct()
{
//set initial tree root to null
\$this->root = null;
\$this->top = null;
}
//print leaf nodes of binary tree
public	function print_leaf_node()
{
if (\$this->root != null)
{
\$temp = \$this->root;
while (\$this->top != null || \$temp != null)
{
if (\$temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (\$temp->left == null && \$temp->right == null)
{
echo " ". \$temp->data ." ";
}
//add tree node into MyStack
\$this->push(\$temp);
//visit left subtree
\$temp = \$temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
\$temp = \$this->top->element;
//remove MyStack element
\$this->pop();
//visit right-subtree
\$temp = \$temp->right;
}
}
}
else
{
echo "Empty Linked List\n";
}
}
//remove top element of stack
public	function push(\$node)
{
\$new_node = new MyStack(\$node);
\$new_node->next = \$this->top;
\$this->top = \$new_node;
}
//remove top element of the stack
public	function pop()
{
if (\$this->top != null)
{
\$remove = \$this->top;
\$this->top = \$this->top->next;
\$remove->next = null;
\$remove->element = null;
\$remove = null;
}
}
}

function main()
{
//Make object of Binary Tree
\$obj = new BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
\$obj->root = new Node(17);
\$obj->root->left = new Node(11);
\$obj->root->right = new Node(21);
\$obj->root->right->right = new Node(9);
\$obj->root->right->right->right = new Node(2);
\$obj->root->right->left = new Node(10);
\$obj->root->left->left = new Node(1);
\$obj->root->left->right = new Node(39);
\$obj->root->left->right->left = new Node(40);
echo "Leaf node is : ";
//Display Tree elements
\$obj->print_leaf_node();
}
main();``````

#### Output

``Leaf node is :  1  40  10  2``
``````/*
Node Js Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
;
//make a tree node
constructor(data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//Define a Stack Class
class MyStack
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print leaf nodes of binary tree
print_leaf_node()
{
if (this.root != null)
{
var temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp.left == null && temp.right == null)
{
process.stdout.write(" " + temp.data + " ");
}
//add tree node into MyStack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = this.top.element;
//remove MyStack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
}
}
//remove top element of stack
push(node)
{
var new_node = new MyStack(node);
new_node.next = this.top;
this.top = new_node;
}
//remove top element of the stack
pop()
{
if (this.top != null)
{
var remove = this.top;
this.top = this.top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
}

function main()
{
//Make object of Binary Tree
var obj = new BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
process.stdout.write("Leaf node is : ");
//Display Tree elements
obj.print_leaf_node();
}
main();``````

#### Output

``Leaf node is :  1  40  10  2``
``````# Python 3 Program
# Print all leaf nodes of a binary tree
# By Using Stack

# Binary Tree node
class Node :

# make a tree node
def __init__(self, data) :
# Assign field values
self.data = data
self.left = None
self.right = None

# Define a Stack Class
class MyStack :

def __init__(self, element) :
self.element = element
self.next = None

class BinaryTree :

def __init__(self) :
# set initial tree root to null
self.root = None
self.top = None

# print leaf nodes of binary tree
def print_leaf_node(self) :
if (self.root != None) :
temp = self.root
while (self.top != None or temp != None) :
if (temp != None) :
# When current temp node of tree is not NULL
# Check that whether node is leaf node or not
if (temp.left == None and temp.right == None) :
print(" ", temp.data ," ", end = "")

# add tree node into MyStack
self.push(temp)
# visit left subtree
temp = temp.left
else :
# When current tree node is NULL
# Fetch a top element of MyStack
temp = self.top.element
# remove MyStack element
self.pop()
# visit right-subtree
temp = temp.right

else :
print("Empty Linked List\n", end = "")

# remove top element of stack
def push(self, node) :
new_node = MyStack(node)
new_node.next = self.top
self.top = new_node

# remove top element of the stack
def pop(self) :
if (self.top != None) :
remove = self.top
self.top = self.top.next
remove.next = None
remove.element = None
remove = None

def main() :
# Make object of Binary Tree
obj = BinaryTree()
#   Make A Binary Tree
# 		-----------------------
# 		        17
# 		      /    \
# 		    11      21
# 		   / \     /  \
# 		  1   39  10   9
# 		     /          \
# 		    40           2
#

# insertion of binary Tree nodes
obj.root = Node(17)
obj.root.left = Node(11)
obj.root.right = Node(21)
obj.root.right.right = Node(9)
obj.root.right.right.right = Node(2)
obj.root.right.left = Node(10)
obj.root.left.left = Node(1)
obj.root.left.right = Node(39)
obj.root.left.right.left = Node(40)
print("Leaf node is : ", end = "")
# Display Tree elements
obj.print_leaf_node()

if __name__ == "__main__": main()``````

#### Output

``Leaf node is :   1    40    10    2``
``````# Ruby Program
# Print all leaf nodes of a binary tree
# By Using Stack

# Binary Tree node
class Node

# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right

# make a tree node
def initialize(data)

# Assign field values
self.data = data
self.left = nil
self.right = nil
end
end
# Define a Stack Class
class MyStack

# Define the accessor and reader of class MyStack
attr_accessor :element, :next

def initialize(element)

self.element = element
self.next = nil
end
end
class BinaryTree

# Define the accessor and reader of class BinaryTree
attr_accessor :root, :top

def initialize()

# set initial tree root to null
self.root = nil
self.top = nil
end
# print leaf nodes of binary tree
def print_leaf_node()

if (self.root != nil)

temp = self.root
while (self.top != nil || temp != nil)

if (temp != nil)

# When current temp node of tree is not NULL
# Check that whether node is leaf node or not
if (temp.left == nil && temp.right == nil)

print(" ", temp.data ," ")
end
# add tree node into MyStack
self.push(temp)
# visit left subtree
temp = temp.left
else

# When current tree node is NULL
# Fetch a top element of MyStack
temp = self.top.element
# remove MyStack element
self.pop()
# visit right-subtree
temp = temp.right
end
end
else

end
end
# remove top element of stack
def push(node)

new_node = MyStack.new(node)
new_node.next = @top
@top = new_node
end
# remove top element of the stack
def pop()

if (@top != nil)

remove = @top
@top = @top.next
remove.next = nil
remove.element = nil
remove = nil
end
end
end
def main()

# Make object of Binary Tree
obj = BinaryTree.new()
#   Make A Binary Tree
# 		-----------------------
# 		        17
# 		      /    \
# 		    11      21
# 		   / \     /  \
# 		  1   39  10   9
# 		     /          \
# 		    40           2
#

# insertion of binary Tree nodes
obj.root = Node.new(17)
obj.root.left = Node.new(11)
obj.root.right = Node.new(21)
obj.root.right.right = Node.new(9)
obj.root.right.right.right = Node.new(2)
obj.root.right.left = Node.new(10)
obj.root.left.left = Node.new(1)
obj.root.left.right = Node.new(39)
obj.root.left.right.left = Node.new(40)
print("Leaf node is : ")
# Display Tree elements
obj.print_leaf_node()
end
main()``````

#### Output

``Leaf node is :  1  40  10  2 ``
``````/*
Scala Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node(var data: Int,
var left: Node,
var right: Node)
{
;
//make a tree node
def this(data: Int)
{
//Assign field values
this(data,null,null);
}
}
//Define a Stack Class
class MyStack(var element: Node,
var next: MyStack)
{
def this(element: Node)
{
this(element,null);
}
}
class BinaryTree(var root: Node,
var top: MyStack)
{
def this()
{
this(null,null);
}
//print leaf nodes of binary tree
def print_leaf_node(): Unit = {
if (this.root != null)
{
var temp: Node = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp.left == null && temp.right == null)
{
print(" " + temp.data + " ");
}
//add tree node into MyStack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = this.top.element;
//remove MyStack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
}
}
//remove top element of stack
def push(node: Node): Unit = {
var new_node: MyStack = new MyStack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
def pop(): Unit = {
if (top != null)
{
var remove: MyStack = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var obj: BinaryTree = new BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
print("Leaf node is : ");
//Display Tree elements
obj.print_leaf_node();
}
}``````

#### Output

``Leaf node is :  1  40  10  2``
``````/*
Swift Program
Print all leaf nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
//make a tree node
init(_ data: Int)
{
//Assign field values
self.data = data;
self.left = nil;
self.right = nil;
}
}
//Define a Stack Class
class MyStack
{
var element: Node? ;
var next: MyStack? ;
init(_ element: Node? )
{
self.element = element;
self.next = nil;
}
}
class BinaryTree
{
var root: Node? ;
var top: MyStack? ;
init()
{
//set initial tree root to null
self.root = nil;
self.top = nil;
}
//print leaf nodes of binary tree
func print_leaf_node()
{
if (self.root != nil)
{
var temp: Node? = self.root;
while (self.top != nil || temp != nil)
{
if (temp != nil)
{
//When current temp node of tree is not NULL
//Check that whether node is leaf node or not
if (temp!.left == nil && temp!.right == nil)
{
print(" ", temp!.data ," ", terminator: "");
}
//add tree node into MyStack
self.push(temp);
//visit left subtree
temp = temp!.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of MyStack
temp = self.top!.element;
//remove MyStack element
self.pop();
//visit right-subtree
temp = temp!.right;
}
}
}
else
{
print("Empty Linked List\n", terminator: "");
}
}
//remove top element of stack
func push(_ node: Node? )
{
let new_node: MyStack? = MyStack(node);
new_node!.next = self.top;
self.top = new_node;
}
//remove top element of the stack
func pop()
{
if (self.top != nil)
{
var remove: MyStack? = self.top;
self.top = self.top!.next;
remove!.next = nil;
remove!.element = nil;
remove = nil;
}
}
}
func main()
{
//Make object of Binary Tree
let obj: BinaryTree = BinaryTree();
/*  Make A Binary Tree
-----------------------
17
/    \
11      21
/ \     /  \
1   39  10   9
/          \
40           2
*/
//insertion of binary Tree nodes
obj.root = Node(17);
obj.root!.left = Node(11);
obj.root!.right = Node(21);
obj.root!.right!.right = Node(9);
obj.root!.right!.right!.right = Node(2);
obj.root!.right!.left = Node(10);
obj.root!.left!.left = Node(1);
obj.root!.left!.right = Node(39);
obj.root!.left!.right!.left = Node(40);
print("Leaf node is : ", terminator: "");
//Display Tree elements
obj.print_leaf_node();
}
main();``````

#### Output

``Leaf node is :   1    40    10    2``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.