Print all leaf nodes of a binary tree using stack
In this problem, we are given a binary tree, and our task is to print all the leaf nodes of the binary tree using a stack. A leaf node is a node that does not have any children (i.e., both left and right child are NULL). We need to traverse the binary tree and collect the leaf nodes using a stack, and then print the collected leaf nodes.
Problem Statement
Given a binary tree, print all the leaf nodes of the binary tree.
Example
Consider the following binary tree:

The leaf nodes of the binary tree are: 1, 40, 10, 2.
Idea to Solve
To print all the leaf nodes of the binary tree, we can use a recursive approach with a stack to collect the leaf nodes. We traverse the binary tree and push each node onto the stack as we move down the tree. When we reach a leaf node (i.e., a node with both left and right children as NULL), we print the node's data, and then remove the node from the stack and continue the traversal.
Algorithm
- Create a class
Node
to represent the binary tree node withdata
,left
, andright
pointers. - Create a class
MyStack
to represent the custom stack withelement
(of typeNode
) andnext
(to point to the next stack element). - Create a class
BinaryTree
withtop
(of typeMyStack
) androot
(of typeNode
) representing the binary tree. - Implement the
push
method inMyStack
to add an element to the top of the stack. - Implement the
pop
method inMyStack
to remove the top element from the stack. - Implement the
print_leaf_node
method inBinaryTree
to print the leaf nodes of the binary tree by traversing the stack and printing the data of leaf nodes. - In the
main
method, create the binary tree and callprint_leaf_node
to print all the leaf nodes.
Standard Pseudocode
Class Node:
data
left
right
Class MyStack:
element (of type Node)
next (of type MyStack)
Function push(node):
new_node = Create a new MyStack node with 'node' as element
new_node.next = top
top = new_node
Function pop():
if top is not empty:
temp = top
top = top.next
temp.next = null
temp.element = null
temp = null
Class BinaryTree:
top (of type MyStack)
root (of type Node)
Function print_leaf_node():
if root is not null:
temp = root
while top is not empty or temp is not null:
if temp is not null:
if temp.left is null and temp.right is null:
Print temp.data
push(temp)
temp = temp.left
else:
temp = top.element
pop()
temp = temp.right
Function main():
obj = Create a new BinaryTree object
Construct the binary tree by inserting nodes
Call obj.print_leaf_node() to print all the leaf nodes
Code Solution
/*
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
{
printf("Empty Linked List\n");
}
}
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
{
System.out.print("Empty Linked List\n");
}
}
//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 header file
#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
{
Console.Write("Empty Linked List\n");
}
}
//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
{
process.stdout.write("Empty Linked List\n");
}
}
//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_reader :element, :next
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_reader :root, :top
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
print("Empty Linked List\n")
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
{
print("Empty Linked List\n");
}
}
//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
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to collect the leaf nodes and print them. The push and pop operations in the stack take constant time, so they do not affect the overall time complexity. Therefore, the time complexity is linear with respect to the number of nodes in the tree.
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.
New Comment