Skip to main content

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:

Print all Leaf nodes of a 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

  1. Create a class Node to represent the binary tree node with data, left, and right pointers.
  2. Create a class MyStack to represent the custom stack with element (of type Node) and next (to point to the next stack element).
  3. Create a class BinaryTree with top (of type MyStack) and root (of type Node) representing the binary tree.
  4. Implement the push method in MyStack to add an element to the top of the stack.
  5. Implement the pop method in MyStack to remove the top element from the stack.
  6. Implement the print_leaf_node method in BinaryTree to print the leaf nodes of the binary tree by traversing the stack and printing the data of leaf nodes.
  7. In the main method, create the binary tree and call print_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.

Last updated on by Kalkicode




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.

New Comment