Check if leaf traversal of two Binary Trees is same or not

Here given code implementation process.

/*
    C Program 
    Check if leaf traversal of two Binary Trees is same or not
*/
#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
struct MyStack
{
	int element;
	struct MyStack *next;
};
//Create a MyStack element and return this reference
struct MyStack *push(int element, struct MyStack **top)
{
	struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (node != NULL)
	{
		//set pointer values
		node->element = element;
		node->next = *top;*top = node;
	}
	else
	{
		printf("Memory Overflow\n");
	}
	return node;
}
//Remove a top node of stack
void pop(struct MyStack **top)
{
	if ( *top != NULL)
	{
		struct MyStack *remove = *top;*top = remove->next;
		remove->next = NULL;
		//free the allocated memory of node
		free(remove);
		remove = NULL;
	}
}
//This is creating a binary tree node and return new node
struct Node *get_node(int data)
{
	// Create dynamic 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;
		new_node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return new_node;
}
//Display pre order elements
void print_preorder(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		print_preorder(node->left);
		print_preorder(node->right);
	}
}
//Collecting leaf node data into stack
void get_leaf_nodes(struct Node *node, struct MyStack **top)
{
	if (node == NULL)
	{
		return;
	}
	else if (node->left == NULL && node->right == NULL)
	{
		push(node->data, top);
		return;
	}
	get_leaf_nodes(node->left, top);
	get_leaf_nodes(node->right, top);
}
//Determine leaf node traversal of both tree are same or not 
void leaf_traversal(struct Node *root1, struct Node *root2)
{
	if (root1 == NULL && root2 == NULL)
	{
		return;
	}
	else
	{
		int status = 1;
		//Display tree elements
		printf("\n First Tree : ");
		print_preorder(root1);
		printf("\n Second Tree : ");
		print_preorder(root2);
		//Define stack variables
		struct MyStack *top1 = NULL;
		struct MyStack *top2 = NULL;
		// Get leaf nodes in trees
		get_leaf_nodes(root1, & top1);
		get_leaf_nodes(root2, & top2);
		//leaf traversal of both stack
		while (top1 != NULL || top2 != NULL)
		{
			if (status == 1 && top1 != NULL && top2 != NULL)
			{
				if (top1->element == top2->element)
				{
					//When leaf node sequence are same
					pop( & top1);
					pop( & top2);
				}
				else
				{
					status = 0;
				}
			}
			else
			{
				// Delete exist stack elements
				if (top1 != NULL)
				{
					pop( & top1);
				}
				if (top2 != NULL)
				{
					pop( & top2);
				}
				status = 0;
			}
		}
		if (status == 1)
		{
			printf("\n Tree Leaf node are same \n");
		}
		else
		{
			printf("\n Tree Leaf node are not same \n");
		}
	}
}
int main()
{
	struct Node *root1 = NULL;
	struct Node *root2 = NULL;
	struct Node *root3 = NULL;
	/* 
	-----------------------
	         6
	        /  \
	       /    \
	      7     11
	     / \    /  \
	    8   1  5    6
	-----------------------
	    First Binary Tree
	     
	*/
	root1 = get_node(6);
	root1->left = get_node(7);
	root1->left->right = get_node(1);
	root1->right = get_node(11);
	root1->right->right = get_node(6);
	root1->right->left = get_node(5);
	root1->left->left = get_node(8);
	/* 
	-----------------------
	         36
	        /  \
	       /    \
	      2      17
	       \    /  \
	        1  5    6
	       / \
	      8   1
	-----------------------
	    Second Binary Tree
	*/
	root2 = get_node(36);
	root2->left = get_node(2);
	root2->left->right = get_node(1);
	root2->right = get_node(17);
	root2->right->right = get_node(6);
	root2->right->left = get_node(5);
	root2->left->right->left = get_node(8);
	root2->left->right->right = get_node(1);
	/* 
	-----------------------
	         36
	        /  \
	       /    \
	      2      17
	       \    /  \
	        1  5    6
	       / \
	      1   8
	-----------------------
	    Third Binary Tree
	*/
	root3 = get_node(36);
	root3->left = get_node(2);
	root3->left->right = get_node(1);
	root3->right = get_node(17);
	root3->right->right = get_node(6);
	root3->right->left = get_node(5);
	root3->left->right->left = get_node(1);
	root3->left->right->right = get_node(8);
	// Test Cases
	leaf_traversal(root1, root2);
	leaf_traversal(root2, root3);
	return 0;
}

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
/*
    Java Program 
    Check if leaf traversal of two Binary Trees is same or not
*/

// Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
//Stack Node
class StackNode
{
	public int element;
	public StackNode next;
	public StackNode(int element)
	{
		this.element = element;
		this.next = null;
	}
}
//Define custom stack and its operation
class MyStack
{
	public StackNode top;
	public MyStack()
	{
		this.top = null;
	}
	//Add a new element in stack
	public void push(int element)
	{
		//Make a new stack node
		StackNode new_node = new StackNode(element);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			System.out.print("Memory overflow\n");
		}
	}
	//remove a top element in stack
	public void pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	//check that whether stack is empty or not
	public boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public int peek()
	{
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 0;
		}
	}
}
//Define Binary Tree 
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		//Set root of tree
		this.root = null;
	}
	//Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print("  " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	//Collecting leaf node data into stack
	public void get_leaf_nodes(Node node, MyStack stack)
	{
		if (node == null)
		{
			return;
		}
		else if (node.left == null && node.right == null)
		{
			stack.push(node.data);
			return;
		}
		get_leaf_nodes(node.left, stack);
		get_leaf_nodes(node.right, stack);
	}
	//Determine leaf node traversal of both tree are same or not 
	public void leaf_traversal(BinaryTree other)
	{
		if (this.root == null && other.root == null)
		{
			return;
		}
		else
		{
			boolean status = true;
			//Display tree elements
			System.out.print("\n First Tree : ");
			print_preorder(this.root);
			System.out.print("\n Second Tree : ");
			print_preorder(other.root);
			//Define stack variables
			MyStack stack1 = new MyStack();
			MyStack stack2 = new MyStack();
			// Get leaf nodes in trees
			get_leaf_nodes(this.root, stack1);
			get_leaf_nodes(other.root, stack2);
			//leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						//When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					// Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				System.out.print("\n Tree Leaf node are same \n");
			}
			else
			{
				System.out.print("\n Tree Leaf node are not same \n");
			}
		}
	}
	public static void main(String[] args)
	{
		//Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/* 
		-----------------------
		         6
		        /  \
		       /    \
		      7     11
		     / \    /  \
		    8   1  5    6
		-----------------------
		First Binary Tree
		     
		*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(7);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(8);
		/* 
		-----------------------
		     36
		    /  \
		   /    \
		  2      17
		   \    /  \
		    1  5    6
		   / \
		  8   1
		-----------------------
		    Second Binary Tree
		*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.right.left = new Node(8);
		tree2.root.left.right.right = new Node(1);
		/* 
		-----------------------
		         36
		        /  \
		       /    \
		      2      17
		       \    /  \
		        1  5    6
		       / \
		      1   8
		-----------------------
		    Third Binary Tree
		*/
		tree3.root = new Node(36);
		tree3.root.left = new Node(2);
		tree3.root.left.right = new Node(1);
		tree3.root.right = new Node(17);
		tree3.root.right.right = new Node(6);
		tree3.root.right.left = new Node(5);
		tree3.root.left.right.left = new Node(1);
		tree3.root.left.right.right = new Node(8);
		// Test Cases
		tree1.leaf_traversal(tree2);
		tree2.leaf_traversal(tree3);
	}
}

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
// Include namespace system
using System;
/*
    C# Program 
    Check if leaf traversal of two Binary Trees is same or not
*/
//  Binary Tree node
public class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Stack Node
public class StackNode
{
	public int element;
	public StackNode next;
	public StackNode(int element)
	{
		this.element = element;
		this.next = null;
	}
}
// Define custom stack and its operation
public class MyStack
{
	public StackNode top;
	public MyStack()
	{
		this.top = null;
	}
	// Add a new element in stack
	public void push(int element)
	{
		// Make a new stack node
		StackNode new_node = new StackNode(element);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			Console.Write("Memory overflow\n");
		}
	}
	// remove a top element in stack
	public void pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	// check that whether stack is empty or not
	public Boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	public int peek()
	{
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 0;
		}
	}
}
// Define Binary Tree
public class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	public void print_preorder(Node node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write("  " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	// Collecting leaf node data into stack
	public void get_leaf_nodes(Node node, MyStack stack)
	{
		if (node == null)
		{
			return;
		}
		else if (node.left == null && node.right == null)
		{
			stack.push(node.data);
			return;
		}
		get_leaf_nodes(node.left, stack);
		get_leaf_nodes(node.right, stack);
	}
	// Determine leaf node traversal of both tree are same or not
	public void leaf_traversal(BinaryTree other)
	{
		if (this.root == null && other.root == null)
		{
			return;
		}
		else
		{
			Boolean status = true;
			// Display tree elements
			Console.Write("\n First Tree : ");
			print_preorder(this.root);
			Console.Write("\n Second Tree : ");
			print_preorder(other.root);
			// Define stack variables
			MyStack stack1 = new MyStack();
			MyStack stack2 = new MyStack();
			//  Get leaf nodes in trees
			get_leaf_nodes(this.root, stack1);
			get_leaf_nodes(other.root, stack2);
			// leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						// When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				Console.Write("\n Tree Leaf node are same \n");
			}
			else
			{
				Console.Write("\n Tree Leaf node are not same \n");
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = new BinaryTree();
		BinaryTree tree3 = new BinaryTree();
		/* 
				-----------------------
				         6
				        /  \
				       /    \
				      7     11
				     / \    /  \
				    8   1  5    6
				-----------------------
				First Binary Tree
				     
		*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(7);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(8);
		/* 
				-----------------------
				     36
				    /  \
				   /    \
				  2      17
				   \    /  \
				    1  5    6
				   / \
				  8   1
				-----------------------
				Second Binary Tree
		*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.right.left = new Node(8);
		tree2.root.left.right.right = new Node(1);
		/* 
				-----------------------
				         36
				        /  \
				       /    \
				      2      17
				       \    /  \
				        1  5    6
				       / \
				      1   8
		   -----------------------
				Third Binary Tree
		*/
		tree3.root = new Node(36);
		tree3.root.left = new Node(2);
		tree3.root.left.right = new Node(1);
		tree3.root.right = new Node(17);
		tree3.root.right.right = new Node(6);
		tree3.root.right.left = new Node(5);
		tree3.root.left.right.left = new Node(1);
		tree3.root.left.right.right = new Node(8);
		//  Test Cases
		tree1.leaf_traversal(tree2);
		tree2.leaf_traversal(tree3);
	}
}

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Check if leaf traversal of two Binary Trees is same or not
*/

//  Binary Tree node
class Node
{
	public: int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//  Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Stack Node
class StackNode
{
	public: int element;
	StackNode *next;
	StackNode(int element)
	{
		this->element = element;
		this->next = NULL;
	}
};
// Define custom stack and its operation
class MyStack
{
	public: StackNode *top;
	MyStack()
	{
		this->top = NULL;
	}
	// Add a new element in stack
	void push(int element)
	{
		// Make a new stack node
		StackNode *new_node = new StackNode(element);
		if (new_node != NULL)
		{
			new_node->next = this->top;
			this->top = new_node;
		}
		else
		{
			cout << "Memory overflow\n";
		}
	}
	// remove a top element in stack
	void pop()
	{
		if (this->top != NULL)
		{
			this->top = this->top->next;
		}
	}
	// check that whether stack is empty or not
	bool is_empty()
	{
		if (this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	int peek()
	{
		if (this->top != NULL)
		{
			return this->top->element;
		}
		else
		{
			return 0;
		}
	}
};
// Define Binary Tree
class BinaryTree
{
	public: Node *root;
	BinaryTree()
	{
		// Set root of tree
		this->root = NULL;
	}
	// Display pre order elements
	void print_preorder(Node *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << "  " << node->data;
			this->print_preorder(node->left);
			this->print_preorder(node->right);
		}
	}
	// Collecting leaf node data into stack
	void get_leaf_nodes(Node *node, MyStack &stack)
	{
		if (node == NULL)
		{
			return;
		}
		else if (node->left == NULL && node->right == NULL)
		{
			stack.push(node->data);
			return;
		}
		this->get_leaf_nodes(node->left, stack);
		this->get_leaf_nodes(node->right, stack);
	}
	// Determine leaf node traversal of both tree are same or not
	void leaf_traversal(BinaryTree other)
	{
		if (this->root == NULL && other.root == NULL)
		{
			return;
		}
		else
		{
			bool status = true;
			// Display tree elements
			cout << "\n First Tree : ";
			this->print_preorder(this->root);
			cout << "\n Second Tree : ";
			this->print_preorder(other.root);
			// Define stack variables
			MyStack stack1 = MyStack();
			MyStack stack2 = MyStack();
			//  Get leaf nodes in trees
			this->get_leaf_nodes(this->root, stack1);
			this->get_leaf_nodes(other.root, stack2);
			// leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						// When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				cout << "\n Tree Leaf node are same \n";
			}
			else
			{
				cout << "\n Tree Leaf node are not same \n";
			}
		}
	}
};
int main()
{
	// Create tree objects
	BinaryTree tree1 = BinaryTree();
	BinaryTree tree2 = BinaryTree();
	BinaryTree tree3 = BinaryTree();
	/*
			-----------------------
			         6
			        /  \
			       /    \
			      7     11
			     / \    /  \
			    8   1  5    6
			-----------------------
			First Binary Tree
			     
			*/
	tree1.root = new Node(6);
	tree1.root->left = new Node(7);
	tree1.root->left->right = new Node(1);
	tree1.root->right = new Node(11);
	tree1.root->right->right = new Node(6);
	tree1.root->right->left = new Node(5);
	tree1.root->left->left = new Node(8);
	/*
			-----------------------
			     36
			    /  \
			   /    \
			  2      17
			   \    /  \
			    1  5    6
			   / \
			  8   1
			-----------------------
			    Second Binary Tree
			*/
	tree2.root = new Node(36);
	tree2.root->left = new Node(2);
	tree2.root->left->right = new Node(1);
	tree2.root->right = new Node(17);
	tree2.root->right->right = new Node(6);
	tree2.root->right->left = new Node(5);
	tree2.root->left->right->left = new Node(8);
	tree2.root->left->right->right = new Node(1);
	/*
			-----------------------
			         36
			        /  \
			       /    \
			      2      17
			       \    /  \
			        1  5    6
			       / \
			      1   8
			-----------------------
			    Third Binary Tree
			*/
	tree3.root = new Node(36);
	tree3.root->left = new Node(2);
	tree3.root->left->right = new Node(1);
	tree3.root->right = new Node(17);
	tree3.root->right->right = new Node(6);
	tree3.root->right->left = new Node(5);
	tree3.root->left->right->left = new Node(1);
	tree3.root->left->right->right = new Node(8);
	//  Test Cases
	tree1.leaf_traversal(tree2);
	tree2.leaf_traversal(tree3);
	return 0;
}

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
<?php
/*
    Php Program 
    Check if leaf traversal of two Binary Trees is same or not
*/
//  Binary Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//  Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
// Stack Node
class StackNode
{
	public $element;
	public $next;

	function __construct($element)
	{
		$this->element = $element;
		$this->next = null;
	}
}
// Define custom stack and its operation
class MyStack
{
	public $top;

	function __construct()
	{
		$this->top = null;
	}
	// Add a new element in stack
	public	function push($element)
	{
		// Make a new stack node
		$new_node = new StackNode($element);
		if ($new_node != null)
		{
			$new_node->next = $this->top;
			$this->top = $new_node;
		}
		else
		{
			echo "Memory overflow\n";
		}
	}
	// remove a top element in stack
	public	function pop()
	{
		if ($this->top != null)
		{
			$this->top = $this->top->next;
		}
	}
	// check that whether stack is empty or not
	public	function is_empty()
	{
		if ($this->top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	public	function peek()
	{
		if ($this->top != null)
		{
			return $this->top->element;
		}
		else
		{
			return 0;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set root of tree
		$this->root = null;
	}
	// Display pre order elements
	public	function print_preorder($node)
	{
		if ($node != null)
		{
			// Print node value
			echo "  ". $node->data;
			$this->print_preorder($node->left);
			$this->print_preorder($node->right);
		}
	}
	// Collecting leaf node data into stack
	public	function get_leaf_nodes($node, $stack)
	{
		if ($node == null)
		{
			return;
		}
		else if ($node->left == null && $node->right == null)
		{
			$stack->push($node->data);
			return;
		}
		$this->get_leaf_nodes($node->left, $stack);
		$this->get_leaf_nodes($node->right, $stack);
	}
	// Determine leaf node traversal of both tree are same or not
	public	function leaf_traversal($other)
	{
		if ($this->root == null && $other->root == null)
		{
			return;
		}
		else
		{
			$status = true;
			// Display tree elements
			echo "\n First Tree : ";
			$this->print_preorder($this->root);
			echo "\n Second Tree : ";
			$this->print_preorder($other->root);
			// Define stack variables
			$stack1 = new MyStack();
			$stack2 = new MyStack();
			//  Get leaf nodes in trees
			$this->get_leaf_nodes($this->root, $stack1);
			$this->get_leaf_nodes($other->root, $stack2);
			// leaf traversal of both stack
			while ($stack1->is_empty() == false || $stack2->is_empty() == false)
			{
				if ($status == true && $stack1->is_empty() == false && $stack2->is_empty() == false)
				{
					if ($stack1->peek() == $stack2->peek())
					{
						// When leaf node sequence are same
						$stack1->pop();
						$stack2->pop();
					}
					else
					{
						$status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if ($stack1->is_empty() == false)
					{
						$stack1->pop();
					}
					if ($stack2->is_empty() == false)
					{
						$stack2->pop();
					}
					$status = false;
				}
			}
			if ($status == true)
			{
				echo "\n Tree Leaf node are same \n";
			}
			else
			{
				echo "\n Tree Leaf node are not same \n";
			}
		}
	}
}

function main()
{
	// Create tree objects
	$tree1 = new BinaryTree();
	$tree2 = new BinaryTree();
	$tree3 = new BinaryTree();
	/* 
	-----------------------
			         6
			        /  \
			       /    \
			      7     11
			     / \    /  \
			    8   1  5    6
	-----------------------
	          First Binary Tree
			     
	*/
	$tree1->root = new Node(6);
	$tree1->root->left = new Node(7);
	$tree1->root->left->right = new Node(1);
	$tree1->root->right = new Node(11);
	$tree1->root->right->right = new Node(6);
	$tree1->root->right->left = new Node(5);
	$tree1->root->left->left = new Node(8);
	/* 
	-----------------------
			     36
			    /  \
			   /    \
			  2      17
			   \    /  \
			    1  5    6
			   / \
			  8   1
	-----------------------
	     Second Binary Tree
	*/
	$tree2->root = new Node(36);
	$tree2->root->left = new Node(2);
	$tree2->root->left->right = new Node(1);
	$tree2->root->right = new Node(17);
	$tree2->root->right->right = new Node(6);
	$tree2->root->right->left = new Node(5);
	$tree2->root->left->right->left = new Node(8);
	$tree2->root->left->right->right = new Node(1);
	/* 
	-----------------------
			         36
			        /  \
			       /    \
			      2      17
			       \    /  \
			        1  5    6
			       / \
			      1   8
	-----------------------
			 Third Binary Tree
	*/
	$tree3->root = new Node(36);
	$tree3->root->left = new Node(2);
	$tree3->root->left->right = new Node(1);
	$tree3->root->right = new Node(17);
	$tree3->root->right->right = new Node(6);
	$tree3->root->right->left = new Node(5);
	$tree3->root->left->right->left = new Node(1);
	$tree3->root->left->right->right = new Node(8);
	//  Test Cases
	$tree1->leaf_traversal($tree2);
	$tree2->leaf_traversal($tree3);
}
main();

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
/*
    Node Js Program 
    Check if leaf traversal of two Binary Trees is same or not
*/

//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Stack Node
class StackNode
{
	constructor(element)
	{
		this.element = element;
		this.next = null;
	}
}
// Define custom stack and its operation
class MyStack
{
	constructor()
	{
		this.top = null;
	}
	// Add a new element in stack
	push(element)
	{
		// Make a new stack node
		var new_node = new StackNode(element);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			process.stdout.write("Memory overflow\n");
		}
	}
	// remove a top element in stack
	pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	// check that whether stack is empty or not
	is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	peek()
	{
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 0;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		// Set root of tree
		this.root = null;
	}
	// Display pre order elements
	print_preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write("  " + node.data);
			this.print_preorder(node.left);
			this.print_preorder(node.right);
		}
	}
	// Collecting leaf node data into stack
	get_leaf_nodes(node, stack)
	{
		if (node == null)
		{
			return;
		}
		else if (node.left == null && node.right == null)
		{
			stack.push(node.data);
			return;
		}
		this.get_leaf_nodes(node.left, stack);
		this.get_leaf_nodes(node.right, stack);
	}
	// Determine leaf node traversal of both tree are same or not
	leaf_traversal(other)
	{
		if (this.root == null && other.root == null)
		{
			return;
		}
		else
		{
			var status = true;
			// Display tree elements
			process.stdout.write("\n First Tree : ");
			this.print_preorder(this.root);
			process.stdout.write("\n Second Tree : ");
			this.print_preorder(other.root);
			// Define stack variables
			var stack1 = new MyStack();
			var stack2 = new MyStack();
			//  Get leaf nodes in trees
			this.get_leaf_nodes(this.root, stack1);
			this.get_leaf_nodes(other.root, stack2);
			// leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						// When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				process.stdout.write("\n Tree Leaf node are same \n");
			}
			else
			{
				process.stdout.write("\n Tree Leaf node are not same \n");
			}
		}
	}
}

function main()
{
	// Create tree objects
	var tree1 = new BinaryTree();
	var tree2 = new BinaryTree();
	var tree3 = new BinaryTree();
	/* 
			-----------------------
			         6
			        /  \
			       /    \
			      7     11
			     / \    /  \
			    8   1  5    6
			-----------------------
			First Binary Tree
			     
			*/
	tree1.root = new Node(6);
	tree1.root.left = new Node(7);
	tree1.root.left.right = new Node(1);
	tree1.root.right = new Node(11);
	tree1.root.right.right = new Node(6);
	tree1.root.right.left = new Node(5);
	tree1.root.left.left = new Node(8);
	/* 
			-----------------------
			     36
			    /  \
			   /    \
			  2      17
			   \    /  \
			    1  5    6
			   / \
			  8   1
			-----------------------
			    Second Binary Tree
			*/
	tree2.root = new Node(36);
	tree2.root.left = new Node(2);
	tree2.root.left.right = new Node(1);
	tree2.root.right = new Node(17);
	tree2.root.right.right = new Node(6);
	tree2.root.right.left = new Node(5);
	tree2.root.left.right.left = new Node(8);
	tree2.root.left.right.right = new Node(1);
	/* 
			-----------------------
			         36
			        /  \
			       /    \
			      2      17
			       \    /  \
			        1  5    6
			       / \
			      1   8
			-----------------------
			    Third Binary Tree
			*/
	tree3.root = new Node(36);
	tree3.root.left = new Node(2);
	tree3.root.left.right = new Node(1);
	tree3.root.right = new Node(17);
	tree3.root.right.right = new Node(6);
	tree3.root.right.left = new Node(5);
	tree3.root.left.right.left = new Node(1);
	tree3.root.left.right.right = new Node(8);
	//  Test Cases
	tree1.leaf_traversal(tree2);
	tree2.leaf_traversal(tree3);
}
main();

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
#     Python 3 Program 
#     Check if leaf traversal of two Binary Trees is same or not

#  Binary Tree node
class Node :
	
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

# Stack Node
class StackNode :
	
	def __init__(self, element) :
		self.element = element
		self.next = None
	

# Define custom stack and its operation
class MyStack :
	
	def __init__(self) :
		self.top = None
	
	# Add a new element in stack
	def push(self, element) :
		# Make a new stack node
		new_node = StackNode(element)
		if (new_node != None) :
			new_node.next = self.top
			self.top = new_node
		else :
			print("Memory overflow\n", end = "")
		
	
	# remove a top element in stack
	def pop(self) :
		if (self.top != None) :
			self.top = self.top.next
		
	
	# check that whether stack is empty or not
	def is_empty(self) :
		if (self.top != None) :
			return False
		else :
			return True
		
	
	# Used to get top element of stack
	def peek(self) :
		if (self.top != None) :
			return self.top.element
		else :
			return 0
		
	

# Define Binary Tree 
class BinaryTree :
	
	def __init__(self) :
		# Set root of tree
		self.root = None
	
	# Display pre order elements
	def print_preorder(self, node) :
		if (node != None) :
			# Print node value
			print("  ", node.data, end = "")
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		
	
	# Collecting leaf node data into stack
	def get_leaf_nodes(self, node, stack) :
		if (node == None) :
			return
		
		elif(node.left == None and node.right == None) :
			stack.push(node.data)
			return
		
		self.get_leaf_nodes(node.left, stack)
		self.get_leaf_nodes(node.right, stack)
	
	# Determine leaf node traversal of both tree are same or not 
	def leaf_traversal(self, other) :
		if (self.root == None and other.root == None) :
			return
		else :
			status = True
			# Display tree elements
			print("\n First Tree : ", end = "")
			self.print_preorder(self.root)
			print("\n Second Tree : ", end = "")
			self.print_preorder(other.root)
			# Define stack variables
			stack1 = MyStack()
			stack2 = MyStack()
			#  Get leaf nodes in trees
			self.get_leaf_nodes(self.root, stack1)
			self.get_leaf_nodes(other.root, stack2)
			# leaf traversal of both stack
			while (stack1.is_empty() == False or stack2.is_empty() == False) :
				if (status == True and stack1.is_empty() == False and stack2.is_empty() == False) :
					if (stack1.peek() == stack2.peek()) :
						# When leaf node sequence are same
						stack1.pop()
						stack2.pop()
					else :
						status = False
					
				else :
					#  Delete exist stack elements
					if (stack1.is_empty() == False) :
						stack1.pop()
					
					if (stack2.is_empty() == False) :
						stack2.pop()
					
					status = False
				
			
			if (status == True) :
				print("\n Tree Leaf node are same \n", end = "")
			else :
				print("\n Tree Leaf node are not same \n", end = "")
			
		
	

def main() :
	# Create tree objects
	tree1 = BinaryTree()
	tree2 = BinaryTree()
	tree3 = BinaryTree()
	#  
	# 		-----------------------
	# 		         6
	# 		        /  \
	# 		       /    \
	# 		      7     11
	# 		     / \    /  \
	# 		    8   1  5    6
	# 		-----------------------
	# 		First Binary Tree
	# 		     
	# 		
	
	tree1.root = Node(6)
	tree1.root.left = Node(7)
	tree1.root.left.right = Node(1)
	tree1.root.right = Node(11)
	tree1.root.right.right = Node(6)
	tree1.root.right.left = Node(5)
	tree1.root.left.left = Node(8)
	#  
	# 		-----------------------
	# 		     36
	# 		    /  \
	# 		   /    \
	# 		  2      17
	# 		   \    /  \
	# 		    1  5    6
	# 		   / \
	# 		  8   1
	# 		-----------------------
	# 		    Second Binary Tree
	# 		
	
	tree2.root = Node(36)
	tree2.root.left = Node(2)
	tree2.root.left.right = Node(1)
	tree2.root.right = Node(17)
	tree2.root.right.right = Node(6)
	tree2.root.right.left = Node(5)
	tree2.root.left.right.left = Node(8)
	tree2.root.left.right.right = Node(1)
	#  
	# 		-----------------------
	# 		         36
	# 		        /  \
	# 		       /    \
	# 		      2      17
	# 		       \    /  \
	# 		        1  5    6
	# 		       / \
	# 		      1   8
	# 		-----------------------
	# 		    Third Binary Tree
	# 		
	
	tree3.root = Node(36)
	tree3.root.left = Node(2)
	tree3.root.left.right = Node(1)
	tree3.root.right = Node(17)
	tree3.root.right.right = Node(6)
	tree3.root.right.left = Node(5)
	tree3.root.left.right.left = Node(1)
	tree3.root.left.right.right = Node(8)
	#  Test Cases
	tree1.leaf_traversal(tree2)
	tree2.leaf_traversal(tree3)

if __name__ == "__main__": main()

Output

 First Tree :    6   7   8   1   11   5   6
 Second Tree :    36   2   1   8   1   17   5   6
 Tree Leaf node are same

 First Tree :    36   2   1   8   1   17   5   6
 Second Tree :    36   2   1   1   8   17   5   6
 Tree Leaf node are not same
#   Ruby Program 
#   Check if leaf traversal of two Binary Trees is same or not

#  Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

# Stack Node
class StackNode  
	# Define the accessor and reader of class StackNode  
	attr_reader :element, :next
	attr_accessor :element, :next
 
	
	def initialize(element) 
		self.element = element
		self.next = nil
	end

end

# Define custom stack and its operation
class MyStack  
	# Define the accessor and reader of class MyStack  
	attr_reader :top
	attr_accessor :top
 
	
	def initialize() 
		self.top = nil
	end

	# Add a new element in stack
	def push(element) 
		# Make a new stack node
		new_node = StackNode.new(element)
		if (new_node != nil) 
			new_node.next = self.top
			self.top = new_node
		else 
			print("Memory overflow\n")
		end

	end

	# remove a top element in stack
	def pop() 
		if (self.top != nil) 
			self.top = self.top.next
		end

	end

	# check that whether stack is empty or not
	def is_empty() 
		if (self.top != nil) 
			return false
		else 
			return true
		end

	end

	# Used to get top element of stack
	def peek() 
		if (self.top != nil) 
			return self.top.element
		else 
			return 0
		end

	end

end

# Define Binary Tree 
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		# Set root of tree
		self.root = nil
	end

	# Display pre order elements
	def print_preorder(node) 
		if (node != nil) 
			# Print node value
			print("  ", node.data)
			self.print_preorder(node.left)
			self.print_preorder(node.right)
		end

	end

	# Collecting leaf node data into stack
	def get_leaf_nodes(node, stack) 
		if (node == nil) 
			return
		elsif(node.left == nil && node.right == nil) 
			stack.push(node.data)
			return
		end

		self.get_leaf_nodes(node.left, stack)
		self.get_leaf_nodes(node.right, stack)
	end

	# Determine leaf node traversal of both tree are same or not 
	def leaf_traversal(other) 
		if (self.root == nil && other.root == nil) 
			return
		else 
			status = true
			# Display tree elements
			print("\n First Tree : ")
			self.print_preorder(self.root)
			print("\n Second Tree : ")
			self.print_preorder(other.root)
			# Define stack variables
			stack1 = MyStack.new()
			stack2 = MyStack.new()
			#  Get leaf nodes in trees
			self.get_leaf_nodes(self.root, stack1)
			self.get_leaf_nodes(other.root, stack2)
			# leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false) 
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false) 
					if (stack1.peek() == stack2.peek()) 
						# When leaf node sequence are same
						stack1.pop()
						stack2.pop()
					else 
						status = false
					end

				else 
					#  Delete exist stack elements
					if (stack1.is_empty() == false) 
						stack1.pop()
					end

					if (stack2.is_empty() == false) 
						stack2.pop()
					end

					status = false
				end

			end

			if (status == true) 
				print("\n Tree Leaf node are same \n")
			else 
				print("\n Tree Leaf node are not same \n")
			end

		end

	end

end

def main() 
	# Create tree objects
	tree1 = BinaryTree.new()
	tree2 = BinaryTree.new()
	tree3 = BinaryTree.new()
	#  
	# 		-----------------------
	# 		         6
	# 		        /  \
	# 		       /    \
	# 		      7     11
	# 		     / \    /  \
	# 		    8   1  5    6
	# 		-----------------------
	# 		First Binary Tree
	# 		     
	# 		
	
	tree1.root = Node.new(6)
	tree1.root.left = Node.new(7)
	tree1.root.left.right = Node.new(1)
	tree1.root.right = Node.new(11)
	tree1.root.right.right = Node.new(6)
	tree1.root.right.left = Node.new(5)
	tree1.root.left.left = Node.new(8)
	#  
	# 		-----------------------
	# 		     36
	# 		    /  \
	# 		   /    \
	# 		  2      17
	# 		   \    /  \
	# 		    1  5    6
	# 		   / \
	# 		  8   1
	# 		-----------------------
	# 		    Second Binary Tree
	# 		
	
	tree2.root = Node.new(36)
	tree2.root.left = Node.new(2)
	tree2.root.left.right = Node.new(1)
	tree2.root.right = Node.new(17)
	tree2.root.right.right = Node.new(6)
	tree2.root.right.left = Node.new(5)
	tree2.root.left.right.left = Node.new(8)
	tree2.root.left.right.right = Node.new(1)
	#  
	# 		-----------------------
	# 		         36
	# 		        /  \
	# 		       /    \
	# 		      2      17
	# 		       \    /  \
	# 		        1  5    6
	# 		       / \
	# 		      1   8
	# 		-----------------------
	# 		    Third Binary Tree
	# 		
	
	tree3.root = Node.new(36)
	tree3.root.left = Node.new(2)
	tree3.root.left.right = Node.new(1)
	tree3.root.right = Node.new(17)
	tree3.root.right.right = Node.new(6)
	tree3.root.right.left = Node.new(5)
	tree3.root.left.right.left = Node.new(1)
	tree3.root.left.right.right = Node.new(8)
	#  Test Cases
	tree1.leaf_traversal(tree2)
	tree2.leaf_traversal(tree3)
end

main()

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same 

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same 
/*
    Scala Program 
    Check if leaf traversal of two Binary Trees is same or not
*/

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Stack Node
class StackNode(var element: Int , var next: StackNode)
{
	def this(element: Int)
	{
		this(element, null);
	}
}
// Define custom stack and its operation
class MyStack(var top: StackNode)
{
	def this()
	{
		this(null);
	}
	// Add a new element in stack
	def push(element: Int): Unit = {
		// Make a new stack node
		var new_node: StackNode = new StackNode(element);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			print("Memory overflow\n");
		}
	}
	// remove a top element in stack
	def pop(): Unit = {
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	// check that whether stack is empty or not
	def is_empty(): Boolean = {
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	def peek(): Int = {
		if (this.top != null)
		{
			return this.top.element;
		}
		else
		{
			return 0;
		}
	}
}
// Define Binary Tree
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Display pre order elements
	def print_preorder(node: Node): Unit = {
		if (node != null)
		{
			// Print node value
			print("  " + node.data);
			print_preorder(node.left);
			print_preorder(node.right);
		}
	}
	// Collecting leaf node data into stack
	def get_leaf_nodes(node: Node, stack: MyStack): Unit = {
		if (node == null)
		{
			return;
		}
		else if (node.left == null && node.right == null)
		{
			stack.push(node.data);
			return;
		}
		get_leaf_nodes(node.left, stack);
		get_leaf_nodes(node.right, stack);
	}
	// Determine leaf node traversal of both tree are same or not
	def leaf_traversal(other: BinaryTree): Unit = {
		if (this.root == null && other.root == null)
		{
			return;
		}
		else
		{
			var status: Boolean = true;
			// Display tree elements
			print("\n First Tree : ");
			print_preorder(this.root);
			print("\n Second Tree : ");
			print_preorder(other.root);
			// Define stack variables
			var stack1: MyStack = new MyStack();
			var stack2: MyStack = new MyStack();
			//  Get leaf nodes in trees
			get_leaf_nodes(this.root, stack1);
			get_leaf_nodes(other.root, stack2);
			// leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						// When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				print("\n Tree Leaf node are same \n");
			}
			else
			{
				print("\n Tree Leaf node are not same \n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree objects
		var tree1: BinaryTree = new BinaryTree();
		var tree2: BinaryTree = new BinaryTree();
		var tree3: BinaryTree = new BinaryTree();
		/* 
				-----------------------
				         6
				        /  \
				       /    \
				      7     11
				     / \    /  \
				    8   1  5    6
				-----------------------
				First Binary Tree
				     
				*/
		tree1.root = new Node(6);
		tree1.root.left = new Node(7);
		tree1.root.left.right = new Node(1);
		tree1.root.right = new Node(11);
		tree1.root.right.right = new Node(6);
		tree1.root.right.left = new Node(5);
		tree1.root.left.left = new Node(8);
		/* 
				-----------------------
				     36
				    /  \
				   /    \
				  2      17
				   \    /  \
				    1  5    6
				   / \
				  8   1
				-----------------------
				    Second Binary Tree
				*/
		tree2.root = new Node(36);
		tree2.root.left = new Node(2);
		tree2.root.left.right = new Node(1);
		tree2.root.right = new Node(17);
		tree2.root.right.right = new Node(6);
		tree2.root.right.left = new Node(5);
		tree2.root.left.right.left = new Node(8);
		tree2.root.left.right.right = new Node(1);
		/* 
				-----------------------
				         36
				        /  \
				       /    \
				      2      17
				       \    /  \
				        1  5    6
				       / \
				      1   8
				-----------------------
				    Third Binary Tree
				*/
		tree3.root = new Node(36);
		tree3.root.left = new Node(2);
		tree3.root.left.right = new Node(1);
		tree3.root.right = new Node(17);
		tree3.root.right.right = new Node(6);
		tree3.root.right.left = new Node(5);
		tree3.root.left.right.left = new Node(1);
		tree3.root.left.right.right = new Node(8);
		//  Test Cases
		tree1.leaf_traversal(tree2);
		tree2.leaf_traversal(tree3);
	}
}

Output

 First Tree :   6  7  8  1  11  5  6
 Second Tree :   36  2  1  8  1  17  5  6
 Tree Leaf node are same

 First Tree :   36  2  1  8  1  17  5  6
 Second Tree :   36  2  1  1  8  17  5  6
 Tree Leaf node are not same
/*
    Swift 4 Program 
    Check if leaf traversal of two Binary Trees is same or not
*/
//  Binary Tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//  Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Stack Node
class StackNode
{
	var element: Int;
	var next: StackNode? ;
	init(_ element: Int)
	{
		self.element = element;
		self.next = nil;
	}
}
// Define custom stack and its operation
class MyStack
{
	var top: StackNode? ;
	init()
	{
		self.top = nil;
	}
	// Add a new element in stack
	func push(_ element: Int)
	{
		// Make a new stack node
		let new_node: StackNode? = StackNode(element);
		if (new_node != nil)
		{
			new_node!.next = self.top;
			self.top = new_node;
		}
		else
		{
			print("Memory overflow\n", terminator: "");
		}
	}
	// remove a top element in stack
	func pop()
	{
		if (self.top != nil)
		{
			self.top = self.top!.next;
		}
	}
	// check that whether stack is empty or not
	func is_empty()->Bool
	{
		if (self.top != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Used to get top element of stack
	func peek()->Int
	{
		if (self.top != nil)
		{
			return self.top!.element;
		}
		else
		{
			return 0;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: Node? ;
	init()
	{
		// Set root of tree
		self.root = nil;
	}
	// Display pre order elements
	func print_preorder(_ node: Node? )
	{
		if (node != nil)
		{
			// Print node value
			print("  ", node!.data, terminator: "");
			self.print_preorder(node!.left);
			self.print_preorder(node!.right);
		}
	}
	// Collecting leaf node data into stack
	func get_leaf_nodes(_ node: Node? , _ stack : MyStack)
	{
		if (node == nil)
		{
			return;
		}
		else if (node!.left == nil && node!.right == nil)
		{
			stack.push(node!.data);
			return;
		}
		self.get_leaf_nodes(node!.left, stack);
		self.get_leaf_nodes(node!.right, stack);
	}
	// Determine leaf node traversal of both tree are same or not
	func leaf_traversal(_ other: BinaryTree? )
	{
		if (self.root == nil && other!.root == nil)
		{
			return;
		}
		else
		{
			var status: Bool = true;
			// Display tree elements
			print("\n First Tree : ", terminator: "");
			self.print_preorder(self.root);
			print("\n Second Tree : ", terminator: "");
			self.print_preorder(other!.root);
			// Define stack variables
			let stack1: MyStack = MyStack();
			let stack2: MyStack = MyStack();
			//  Get leaf nodes in trees
			self.get_leaf_nodes(self.root, stack1);
			self.get_leaf_nodes(other!.root, stack2);
			// leaf traversal of both stack
			while (stack1.is_empty() == false || stack2.is_empty() == false)
			{
				if (status == true && stack1.is_empty() == false && stack2.is_empty() == false)
				{
					if (stack1.peek() == stack2.peek())
					{
						// When leaf node sequence are same
						stack1.pop();
						stack2.pop();
					}
					else
					{
						status = false;
					}
				}
				else
				{
					//  Delete exist stack elements
					if (stack1.is_empty() == false)
					{
						stack1.pop();
					}
					if (stack2.is_empty() == false)
					{
						stack2.pop();
					}
					status = false;
				}
			}
			if (status == true)
			{
				print("\n Tree Leaf node are same \n", terminator: "");
			}
			else
			{
				print("\n Tree Leaf node are not same \n", terminator: "");
			}
		}
	}
}
func main()
{
	// Create tree objects
	let tree1: BinaryTree = BinaryTree();
	let tree2: BinaryTree = BinaryTree();
	let tree3: BinaryTree? = BinaryTree();
	/* 
		-----------------------
		         6
		        /  \
		       /    \
		      7     11
		     / \    /  \
		    8   1  5    6
		-----------------------
		First Binary Tree
		     
		*/
	tree1.root = Node(6);
	tree1.root!.left = Node(7);
	tree1.root!.left!.right = Node(1);
	tree1.root!.right = Node(11);
	tree1.root!.right!.right = Node(6);
	tree1.root!.right!.left = Node(5);
	tree1.root!.left!.left = Node(8);
	/* 
		-----------------------
		     36
		    /  \
		   /    \
		  2      17
		   \    /  \
		    1  5    6
		   / \
		  8   1
		-----------------------
		    Second Binary Tree
		*/
	tree2.root = Node(36);
	tree2.root!.left = Node(2);
	tree2.root!.left!.right = Node(1);
	tree2.root!.right = Node(17);
	tree2.root!.right!.right = Node(6);
	tree2.root!.right!.left = Node(5);
	tree2.root!.left!.right!.left = Node(8);
	tree2.root!.left!.right!.right = Node(1);
	/* 
		-----------------------
		         36
		        /  \
		       /    \
		      2      17
		       \    /  \
		        1  5    6
		       / \
		      1   8
		-----------------------
		    Third Binary Tree
		*/
	tree3!.root = Node(36);
	tree3!.root!.left = Node(2);
	tree3!.root!.left!.right = Node(1);
	tree3!.root!.right = Node(17);
	tree3!.root!.right!.right = Node(6);
	tree3!.root!.right!.left = Node(5);
	tree3!.root!.left!.right!.left = Node(1);
	tree3!.root!.left!.right!.right = Node(8);
	//  Test Cases
	tree1.leaf_traversal(tree2);
	tree2.leaf_traversal(tree3);
}
main();

Output

 First Tree :    6   7   8   1   11   5   6
 Second Tree :    36   2   1   8   1   17   5   6
 Tree Leaf node are same

 First Tree :    36   2   1   8   1   17   5   6
 Second Tree :    36   2   1   1   8   17   5   6
 Tree Leaf node are not same


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