Size of binary tree without recursion

Here given code implementation process.

/*
    C Program 
    Size of binary tree without recursion
*/
#include <stdio.h>
#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};

//This is creating a binary tree node and return this
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;
}

// Returns the number of element in given binary tree
int tree_size(struct Node *root)
{
	int size = 0;
	// Start to root node of tree
	struct Node *current = root;
	struct Node *auxiliary = NULL;
	//iterating tree nodes
	while (current != NULL)
	{
		if (current->left == NULL)
		{
			// When left child are empty then visit to right child
			current = current->right;
			size++;
		}
		else
		{
			// Start to left child
			auxiliary = current->left;
			while (auxiliary->right != NULL && auxiliary->right != current)
			{
				auxiliary = auxiliary->right;
			}
			if (auxiliary->right == NULL)
			{
				// Change link
				auxiliary->right = current;
				current = current->left;
			}
			else
			{
				// Unlink
				auxiliary->right = NULL;
				// Visit to right child
				current = current->right;
				// Count node
				size++;
			}
		}
	}
	return size;
}

int main()
{
	struct Node *root = NULL;
	/*Create Binary Tree
	-----------------------
	        5
	       /  \
	      2    4
	     /    /  \
	    7    6    3
	     \
	      -3
	*/
	//Add tree node
	root = get_node(5);
	root->left = get_node(2);
	root->right = get_node(4);
	root->right->right = get_node(3);
	root->right->left = get_node(6);
	root->left->left = get_node(7);
	root->left->left->right = get_node(-3);
	int size = tree_size(root);
	printf(" Tree Size : %d \n", size);
	return 0;
}

Output

 Tree Size : 7
/* 
  Java Program 
  Size of binary tree without recursion
*/

//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;
	}
}
class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	// Returns the number of element in given binary tree
	public int tree_size(Node root)
	{
		int size = 0;
		// Start to root node of tree
		Node current = root;
		Node auxiliary = null;
		//iterating tree nodes
		while (current != null)
		{
			if (current.left == null)
			{
				// When left child are empty then visit to right child
				current = current.right;
				size++;
			}
			else
			{
				// Start to left child
				auxiliary = current.left;
				while (auxiliary.right != null && auxiliary.right != current)
				{
					auxiliary = auxiliary.right;
				}
				if (auxiliary.right == null)
				{
					// Change link
					auxiliary.right = current;
					current = current.left;
				}
				else
				{
					// Unlink
					auxiliary.right = null;
					// Visit to right child
					current = current.right;
					// Count node
					size++;
				}
			}
		}
		return size;
	}
	public static void main(String[] args)
	{
		//Make object of binary tree
		BinaryTree tree = new BinaryTree();
		/* 
		Create Binary Tree
		-----------------------
		        5
		       /  \
		      2    4
		     /    /  \
		    7    6    3
		     \
		      -3
		*/
		//Add tree node
		tree.root = new Node(5);
		tree.root.left = new Node(2);
		tree.root.right = new Node(4);
		tree.root.right.right = new Node(3);
		tree.root.right.left = new Node(6);
		tree.root.left.left = new Node(7);
		tree.root.left.left.right = new Node(-3);
		int size = tree.tree_size(tree.root);
		System.out.print(" Tree Size : " + size + " \n");
	}
}

Output

 Tree Size : 7
//Include header file
#include <iostream>
using namespace std;

/*
  C++ Program 
  Size of binary tree without recursion
*/

//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;
	}
};
class BinaryTree
{
	public: Node *root;
	BinaryTree()
	{
		// Set initial tree root to null
		this->root = NULL;
	}
	// Returns the number of element in given binary tree
	int tree_size(Node *root)
	{
		int size = 0;
		// Start to root node of tree
		Node *current = root;
		Node *auxiliary = NULL;
		//iterating tree nodes
		while (current != NULL)
		{
			if (current->left == NULL)
			{
				// When left child are empty then visit to right child
				current = current->right;
				size++;
			}
			else
			{
				// Start to left child
				auxiliary = current->left;
				while (auxiliary->right != NULL && auxiliary->right != current)
				{
					auxiliary = auxiliary->right;
				}
				if (auxiliary->right == NULL)
				{
					// Change link
					auxiliary->right = current;
					current = current->left;
				}
				else
				{
					// Count node
					// Unlink
					auxiliary->right = NULL;
					// Visit to right child
					current = current->right;
					size++;
				}
			}
		}
		return size;
	}
};
int main()
{
	//Make object of binary tree
	BinaryTree tree = BinaryTree();
	/*
			Create Binary Tree
			-----------------------
			        5
			       /  \
			      2    4
			     /    /  \
			    7    6    3
			     \
			      -3
			*/
	//Add tree node
	tree.root = new Node(5);
	tree.root->left = new Node(2);
	tree.root->right = new Node(4);
	tree.root->right->right = new Node(3);
	tree.root->right->left = new Node(6);
	tree.root->left->left = new Node(7);
	tree.root->left->left->right = new Node(-3);
	int size = tree.tree_size(tree.root);
	cout << " Tree Size : " << size << " \n";
	return 0;
}

Output

 Tree Size : 7
//Include namespace system
using System;

/* 
  C# Program 
  Size of binary tree without recursion
*/

//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;
	}
}
class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	// Returns the number of element in given binary tree
	public int tree_size(Node root)
	{
		int size = 0;
		// Start to root node of tree
		Node current = root;
		Node auxiliary = null;
		//iterating tree nodes
		while (current != null)
		{
			if (current.left == null)
			{
				// When left child are empty then visit to right child
				current = current.right;
				size++;
			}
			else
			{
				// Start to left child
				auxiliary = current.left;
				while (auxiliary.right != null && auxiliary.right != current)
				{
					auxiliary = auxiliary.right;
				}
				if (auxiliary.right == null)
				{
					// Change link
					auxiliary.right = current;
					current = current.left;
				}
				else
				{
					// Count node
					// Unlink
					auxiliary.right = null;
					// Visit to right child
					current = current.right;
					size++;
				}
			}
		}
		return size;
	}
	public static void Main(String[] args)
	{
		//Make object of binary tree
		BinaryTree tree = new BinaryTree();
		/* 
				Create Binary Tree
				-----------------------
				        5
				       /  \
				      2    4
				     /    /  \
				    7    6    3
				     \
				      -3
				*/
		//Add tree node
		tree.root = new Node(5);
		tree.root.left = new Node(2);
		tree.root.right = new Node(4);
		tree.root.right.right = new Node(3);
		tree.root.right.left = new Node(6);
		tree.root.left.left = new Node(7);
		tree.root.left.left.right = new Node(-3);
		int size = tree.tree_size(tree.root);
		Console.Write(" Tree Size : " + size + " \n");
	}
}

Output

 Tree Size : 7
<?php
/* 
  Php Program 
  Size of binary tree without recursion
*/

//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;
	}
}
class BinaryTree
{
	public $root;

	function __construct()
	{
		// Set initial tree root to null
		$this->root = null;
	}
	// Returns the number of element in given binary tree
	public	function tree_size($root)
	{
		$size = 0;
		// Start to root node of tree
		$current = $root;
		$auxiliary = null;
		//iterating tree nodes
		while ($current != null)
		{
			if ($current->left == null)
			{
				// When left child are empty then visit to right child
				$current = $current->right;
				$size++;
			}
			else
			{
				// Start to left child
				$auxiliary = $current->left;
				while ($auxiliary->right != null && $auxiliary->right != $current)
				{
					$auxiliary = $auxiliary->right;
				}
				if ($auxiliary->right == null)
				{
					// Change link
					$auxiliary->right = $current;
					$current = $current->left;
				}
				else
				{
					// Count node
					// Unlink
					$auxiliary->right = null;
					// Visit to right child
					$current = $current->right;
					$size++;
				}
			}
		}
		return $size;
	}
}

function main()
{
	//Make object of binary tree
	$tree = new BinaryTree();
	/* 
			Create Binary Tree
			-----------------------
			        5
			       /  \
			      2    4
			     /    /  \
			    7    6    3
			     \
			      -3
			*/
	//Add tree node
	$tree->root = new Node(5);
	$tree->root->left = new Node(2);
	$tree->root->right = new Node(4);
	$tree->root->right->right = new Node(3);
	$tree->root->right->left = new Node(6);
	$tree->root->left->left = new Node(7);
	$tree->root->left->left->right = new Node(-3);
	$size = $tree->tree_size($tree->root);
	echo " Tree Size : ". $size ." \n";
}
main();

Output

 Tree Size : 7
/* 
  Node Js Program 
  Size of binary tree without recursion
*/
//Binary Tree node
class Node
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		// Set initial tree root to null
		this.root = null;
	}
	// Returns the number of element in given binary tree
	tree_size(root)
	{
		var size = 0;
		// Start to root node of tree
		var current = root;
		var auxiliary = null;
		//iterating tree nodes
		while (current != null)
		{
			if (current.left == null)
			{
				// When left child are empty then visit to right child
				current = current.right;
				size++;
			}
			else
			{
				// Start to left child
				auxiliary = current.left;
				while (auxiliary.right != null && auxiliary.right != current)
				{
					auxiliary = auxiliary.right;
				}
				if (auxiliary.right == null)
				{
					// Change link
					auxiliary.right = current;
					current = current.left;
				}
				else
				{
					// Count node
					// Unlink
					auxiliary.right = null;
					// Visit to right child
					current = current.right;
					size++;
				}
			}
		}
		return size;
	}
}

function main()
{
	//Make object of binary tree
	var tree = new BinaryTree();
	/* 
			Create Binary Tree
			-----------------------
			        5
			       /  \
			      2    4
			     /    /  \
			    7    6    3
			     \
			      -3
			*/
	//Add tree node
	tree.root = new Node(5);
	tree.root.left = new Node(2);
	tree.root.right = new Node(4);
	tree.root.right.right = new Node(3);
	tree.root.right.left = new Node(6);
	tree.root.left.left = new Node(7);
	tree.root.left.left.right = new Node(-3);
	var size = tree.tree_size(tree.root);
	process.stdout.write(" Tree Size : " + size + " \n");
}
main();

Output

 Tree Size : 7
#   Python 3 Program 
#   Size of binary tree without recursion

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

class BinaryTree :
	
	def __init__(self) :
		#  Set initial tree root to null
		self.root = None
	
	#  Returns the number of element in given binary tree
	def tree_size(self, root) :
		size = 0
		#  Start to root node of tree
		current = root
		auxiliary = None
		# iterating tree nodes
		while (current != None) :
			if (current.left == None) :
				#  When left child are empty then visit to right child
				current = current.right
				size += 1
			else :
				#  Start to left child
				auxiliary = current.left
				while (auxiliary.right != None and auxiliary.right != current) :
					auxiliary = auxiliary.right
				
				if (auxiliary.right == None) :
					#  Change link
					auxiliary.right = current
					current = current.left
				else :
					#  Unlink
					auxiliary.right = None
					#  Visit to right child
					current = current.right
					#  Count node
					size += 1
				
			
		
		return size
	

def main() :
	# Make object of binary tree
	tree = BinaryTree()
	#  
	# 		Create Binary Tree
	# 		-----------------------
	# 		        5
	# 		       /  \
	# 		      2    4
	# 		     /    /  \
	# 		    7    6    3
	# 		     \
	# 		      -3
	# 		
	
	# Add tree node
	tree.root = Node(5)
	tree.root.left = Node(2)
	tree.root.right = Node(4)
	tree.root.right.right = Node(3)
	tree.root.right.left = Node(6)
	tree.root.left.left = Node(7)
	tree.root.left.left.right = Node(-3)
	size = tree.tree_size(tree.root)
	print(" Tree Size : ", size ," \n", end = "")

if __name__ == "__main__": main()

Output

 Tree Size :  7
#   Ruby Program 
#   Size of binary tree without recursion

# 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

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

	#  Returns the number of element in given binary tree
	def tree_size(root) 
		size = 0
		#  Start to root node of tree
		current = root
		auxiliary = nil
		# iterating tree nodes
		while (current != nil) 
			if (current.left == nil) 
				#  When left child are empty then visit to right child
				current = current.right
				size += 1
			else 
				#  Start to left child
				auxiliary = current.left
				while (auxiliary.right != nil && auxiliary.right != current) 
					auxiliary = auxiliary.right
				end

				if (auxiliary.right == nil) 
					#  Change link
					auxiliary.right = current
					current = current.left
				else 
					#  Unlink
					auxiliary.right = nil
					#  Visit to right child
					current = current.right
					#  Count node
					size += 1
				end

			end

		end

		return size
	end

end

def main() 
	# Make object of binary tree
	tree = BinaryTree.new()
	#  
	# 		Create Binary Tree
	# 		-----------------------
	# 		        5
	# 		       /  \
	# 		      2    4
	# 		     /    /  \
	# 		    7    6    3
	# 		     \
	# 		      -3
	# 		
	
	# Add tree node
	tree.root = Node.new(5)
	tree.root.left = Node.new(2)
	tree.root.right = Node.new(4)
	tree.root.right.right = Node.new(3)
	tree.root.right.left = Node.new(6)
	tree.root.left.left = Node.new(7)
	tree.root.left.left.right = Node.new(-3)
	size = tree.tree_size(tree.root)
	print(" Tree Size : ", size ," \n")
end

main()

Output

 Tree Size : 7 
/* 
  Scala Program 
  Size of binary tree without recursion
*/

//Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Returns the number of element in given binary tree
	def tree_size(root: Node): Int = {
		var size: Int = 0;
		// Start to root node of tree
		var current: Node = root;
		var auxiliary: Node = null;
		//iterating tree nodes
		while (current != null)
		{
			if (current.left == null)
			{
				// When left child are empty then visit to right child
				current = current.right;
				size += 1;
			}
			else
			{
				// Start to left child
				auxiliary = current.left;
				while (auxiliary.right != null && auxiliary.right != current)
				{
					auxiliary = auxiliary.right;
				}
				if (auxiliary.right == null)
				{
					// Change link
					auxiliary.right = current;
					current = current.left;
				}
				else
				{
					// Count node
					// Unlink
					auxiliary.right = null;
					// Visit to right child
					current = current.right;
					size += 1;
				}
			}
		}
		return size;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of binary tree
		var tree: BinaryTree = new BinaryTree();
		/* 
				Create Binary Tree
				-----------------------
				        5
				       /  \
				      2    4
				     /    /  \
				    7    6    3
				     \
				      -3
				*/
		//Add tree node
		tree.root = new Node(5);
		tree.root.left = new Node(2);
		tree.root.right = new Node(4);
		tree.root.right.right = new Node(3);
		tree.root.right.left = new Node(6);
		tree.root.left.left = new Node(7);
		tree.root.left.left.right = new Node(-3);
		var size: Int = tree.tree_size(tree.root);
		print(" Tree Size : " + size + " \n");
	}
}

Output

 Tree Size : 7
/* 
  Swift 4 Program 
  Size of binary tree without recursion
*/
//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;
	}
}
class BinaryTree
{
	var root: Node? ;
	init()
	{
		// Set initial tree root to null
		self.root = nil;
	}
	// Returns the number of element in given binary tree
	func tree_size(_ root: Node? )->Int
	{
		var size: Int = 0;
		// Start to root node of tree
		var current: Node? = root;
		var auxiliary: Node? = nil;
		//iterating tree nodes
		while (current != nil)
		{
			if (current!.left == nil)
			{
				// When left child are empty then visit to right child
				current = current!.right;
				size += 1;
			}
			else
			{
				// Start to left child
				auxiliary = current!.left;
				while (auxiliary!.right != nil && !(auxiliary!.right === current))
				{
					auxiliary = auxiliary!.right;
				}
				if (auxiliary!.right == nil)
				{
					// Change link
					auxiliary!.right = current;
					current = current!.left;
				}
				else
				{
					// Count node
					// Unlink
					auxiliary!.right = nil;
					// Visit to right child
					current = current!.right;
					size += 1;
				}
			}
		}
		return size;
	}
}
func main()
{
	//Make object of binary tree
	let tree: BinaryTree = BinaryTree();
	/* 
			Create Binary Tree
			-----------------------
			        5
			       /  \
			      2    4
			     /    /  \
			    7    6    3
			     \
			      -3
			*/
	//Add tree node
	tree.root = Node(5);
	tree.root!.left = Node(2);
	tree.root!.right = Node(4);
	tree.root!.right!.right = Node(3);
	tree.root!.right!.left = Node(6);
	tree.root!.left!.left = Node(7);
	tree.root!.left!.left!.right = Node(-3);
	let size: Int = tree.tree_size(tree.root);
	print(" Tree Size : ", size ," \n", terminator: "");
}
main();

Output

 Tree Size :  7


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