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.

Print all Leaf nodes of a binary tree

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
	{
		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


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







© 2021, kalkicode.com, All rights reserved