Skip to main content

Check whether a binary tree is a full binary tree or not

Here given code implementation process.

/*
    C Program 
    Check whether a binary tree is a full binary tree or not
*/
#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 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);
	}
}
// Check that whether given binary tree is full binary tree or not
int check_full_binary_tree(struct Node *node)
{
	if (node == NULL || node->left == NULL && node->right == NULL)
	{
		// When node is null and node is leaf node
		return 1;
	}
	else if (node->left == NULL || node->right == NULL)
	{
		return 0;
	}
	return check_full_binary_tree(node->left) && check_full_binary_tree(node->right);
}
// Handles the request of to find full binary tree 
void is_full_binary_tree(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	else
	{
		//Display tree elements
		printf("\n Tree Node : ");
		print_preorder(root);
		if (check_full_binary_tree(root))
		{
			printf("\n Is full binary tree \n");
		}
		else
		{
			printf("\n Is not full binary tree \n");
		}
	}
}
int main()
{
	// Define pointer
	struct Node *root1 = NULL;
	struct Node *root2 = 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   7
	-----------------------
	    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(7);
	// Test Cases
	is_full_binary_tree(root1);
	is_full_binary_tree(root2);
	return 0;
}

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
/*
    Java Program 
    Check whether a binary tree is a full binary tree 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;
	}
}
//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);
		}
	}
	// Check that whether given binary tree is full binary tree or not
	public boolean check_full_binary_tree(Node node)
	{
		if (node == null || node.left == null && node.right == null)
		{
			// When node is null and node is leaf node
			return true;
		}
		else if (node.left == null || node.right == null)
		{
			return false;
		}
		return check_full_binary_tree(node.left) && check_full_binary_tree(node.right);
	}
	// Handles the request of to find full binary tree 
	public void is_full_binary_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			//Display tree elements
			System.out.print("\n Tree Node : ");
			print_preorder(this.root);
			if (check_full_binary_tree(this.root))
			{
				System.out.print("\n Is full binary tree \n");
			}
			else
			{
				System.out.print("\n Is not full binary tree \n");
			}
		}
	}
	public static void main(String[] args)
	{
		//Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = 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   7
		-----------------------
		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(7);
		// Test Cases
		tree1.is_full_binary_tree();
		tree2.is_full_binary_tree();
	}
}

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program 
    Check whether a binary tree is a full binary tree 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;
	}
};
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	bool check_full_binary_tree(Node *node)
	{
		if (node == NULL || node->left == NULL && node->right == NULL)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if (node->left == NULL || node->right == NULL)
		{
			return false;
		}
		return this->check_full_binary_tree(node->left) && this->check_full_binary_tree(node->right);
	}
	//  Handles the request of to find full binary tree
	void is_full_binary_tree()
	{
		if (this->root == NULL)
		{
			return;
		}
		else
		{
			// Display tree elements
			cout << "\n Tree Node : ";
			this->print_preorder(this->root);
			if (this->check_full_binary_tree(this->root))
			{
				cout << "\n Is full binary tree \n";
			}
			else
			{
				cout << "\n Is not full binary tree \n";
			}
		}
	}
};
int main()
{
	// Create tree objects
	BinaryTree tree1 = BinaryTree();
	BinaryTree tree2 = 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   7
			-----------------------
			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(7);
	//  Test Cases
	tree1.is_full_binary_tree();
	tree2.is_full_binary_tree();
	return 0;
}

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
// Include namespace system
using System;

/*
    C# Program 
    Check whether a binary tree is a full binary tree 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;
	}
}
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	public Boolean check_full_binary_tree(Node node)
	{
		if (node == null || node.left == null && node.right == null)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if (node.left == null || node.right == null)
		{
			return false;
		}
		return check_full_binary_tree(node.left) && check_full_binary_tree(node.right);
	}
	//  Handles the request of to find full binary tree
	public void is_full_binary_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			// Display tree elements
			Console.Write("\n Tree Node : ");
			print_preorder(this.root);
			if (check_full_binary_tree(this.root))
			{
				Console.Write("\n Is full binary tree \n");
			}
			else
			{
				Console.Write("\n Is not full binary tree \n");
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create tree objects
		BinaryTree tree1 = new BinaryTree();
		BinaryTree tree2 = 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   7
				-----------------------
				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(7);
		//  Test Cases
		tree1.is_full_binary_tree();
		tree2.is_full_binary_tree();
	}
}

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
<?php
/*
    Php Program 
    Check whether a binary tree is a full binary tree 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;
	}
}
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	public	function check_full_binary_tree($node)
	{
		if ($node == null || $node->left == null && $node->right == null)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if ($node->left == null || $node->right == null)
		{
			return false;
		}
		return $this->check_full_binary_tree($node->left) && $this->check_full_binary_tree($node->right);
	}
	//  Handles the request of to find full binary tree
	public	function is_full_binary_tree()
	{
		if ($this->root == null)
		{
			return;
		}
		else
		{
			// Display tree elements
			echo "\n Tree Node : ";
			$this->print_preorder($this->root);
			if ($this->check_full_binary_tree($this->root))
			{
				echo "\n Is full binary tree \n";
			}
			else
			{
				echo "\n Is not full binary tree \n";
			}
		}
	}
}

function main()
{
	// Create tree objects
	$tree1 = new BinaryTree();
	$tree2 = 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   7
			-----------------------
			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(7);
	//  Test Cases
	$tree1->is_full_binary_tree();
	$tree2->is_full_binary_tree();
}
main();

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
/*
    Node Js Program 
    Check whether a binary tree is a full binary tree or not
*/
//  Binary Tree node
class Node
{
	constructor(data)
	{
		//  Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	check_full_binary_tree(node)
	{
		if (node == null || node.left == null && node.right == null)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if (node.left == null || node.right == null)
		{
			return false;
		}
		return this.check_full_binary_tree(node.left) && this.check_full_binary_tree(node.right);
	}
	//  Handles the request of to find full binary tree
	is_full_binary_tree()
	{
		if (this.root == null)
		{
			return;
		}
		else
		{
			// Display tree elements
			process.stdout.write("\n Tree Node : ");
			this.print_preorder(this.root);
			if (this.check_full_binary_tree(this.root))
			{
				process.stdout.write("\n Is full binary tree \n");
			}
			else
			{
				process.stdout.write("\n Is not full binary tree \n");
			}
		}
	}
}

function main()
{
	// Create tree objects
	var tree1 = new BinaryTree();
	var tree2 = 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   7
			-----------------------
			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(7);
	//  Test Cases
	tree1.is_full_binary_tree();
	tree2.is_full_binary_tree();
}
main();

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
#  Python 3 Program 
#  Check whether a binary tree is a full binary tree or not

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

# 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)
		
	
	#  Check that whether given binary tree is full binary tree or not
	def check_full_binary_tree(self, node) :
		if (node == None or node.left == None and node.right == None) :
			#  When node is null and node is leaf node
			return True
		
		elif(node.left == None or node.right == None) :
			return False
		
		return self.check_full_binary_tree(node.left) and self.check_full_binary_tree(node.right)
	
	#  Handles the request of to find full binary tree 
	def is_full_binary_tree(self) :
		if (self.root == None) :
			return
		else :
			# Display tree elements
			print("\n Tree Node : ", end = "")
			self.print_preorder(self.root)
			if (self.check_full_binary_tree(self.root)) :
				print("\n Is full binary tree \n", end = "")
			else :
				print("\n Is not full binary tree \n", end = "")
			
		
	

def main() :
	# Create tree objects
	tree1 = BinaryTree()
	tree2 = 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   7
	# 		-----------------------
	# 		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(7)
	#  Test Cases
	tree1.is_full_binary_tree()
	tree2.is_full_binary_tree()

if __name__ == "__main__": main()

Output

 Tree Node :    6   7   8   1   11   5   6
 Is full binary tree

 Tree Node :    36   2   1   8   7   17   5   6
 Is not full binary tree
#  Ruby Program 
#  Check whether a binary tree is a full binary tree 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

# 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

	#  Check that whether given binary tree is full binary tree or not
	def check_full_binary_tree(node) 
		if (node == nil || node.left == nil && node.right == nil) 
			#  When node is null and node is leaf node
			return true
		elsif(node.left == nil || node.right == nil) 
			return false
		end

		return self.check_full_binary_tree(node.left) && self.check_full_binary_tree(node.right)
	end

	#  Handles the request of to find full binary tree 
	def is_full_binary_tree() 
		if (self.root == nil) 
			return
		else 
			# Display tree elements
			print("\n Tree Node : ")
			self.print_preorder(self.root)
			if (self.check_full_binary_tree(self.root)) 
				print("\n Is full binary tree \n")
			else 
				print("\n Is not full binary tree \n")
			end

		end

	end

end

def main() 
	# Create tree objects
	tree1 = BinaryTree.new()
	tree2 = 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   7
	# 		-----------------------
	# 		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(7)
	#  Test Cases
	tree1.is_full_binary_tree()
	tree2.is_full_binary_tree()
end

main()

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree 

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree 

/*
    Scala Program 
    Check whether a binary tree is a full binary tree or not
*/

//  Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	def check_full_binary_tree(node: Node): Boolean = {
		if (node == null || node.left == null && node.right == null)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if (node.left == null || node.right == null)
		{
			return false;
		}
		return check_full_binary_tree(node.left) && check_full_binary_tree(node.right);
	}
	//  Handles the request of to find full binary tree
	def is_full_binary_tree(): Unit = {
		if (this.root == null)
		{
			return;
		}
		else
		{
			// Display tree elements
			print("\n Tree Node : ");
			print_preorder(this.root);
			if (check_full_binary_tree(this.root))
			{
				print("\n Is full binary tree \n");
			}
			else
			{
				print("\n Is not full binary tree \n");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create tree objects
		var tree1: BinaryTree = new BinaryTree();
		var tree2: 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   7
				-----------------------
				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(7);
		//  Test Cases
		tree1.is_full_binary_tree();
		tree2.is_full_binary_tree();
	}
}

Output

 Tree Node :   6  7  8  1  11  5  6
 Is full binary tree

 Tree Node :   36  2  1  8  7  17  5  6
 Is not full binary tree
/*
    Swift 4 Program 
    Check whether a binary tree is a full binary tree 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;
	}
}
// 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);
		}
	}
	//  Check that whether given binary tree is full binary tree or not
	func check_full_binary_tree(_ node: Node? )->Bool
	{
		if (node == nil || node!.left == nil && node!.right == nil)
		{
			//  When node is null and node is leaf node
			return true;
		}
		else if (node!.left == nil || node!.right == nil)
		{
			return false;
		}
		return self.check_full_binary_tree(node!.left) && self.check_full_binary_tree(node!.right);
	}
	//  Handles the request of to find full binary tree
	func is_full_binary_tree()
	{
		if (self.root == nil)
		{
			return;
		}
		else
		{
			// Display tree elements
			print("\n Tree Node : ", terminator: "");
			self.print_preorder(self.root);
			if (self.check_full_binary_tree(self.root))
			{
				print("\n Is full binary tree ");
			}
			else
			{
				print("\n Is not full binary tree ");
			}
		}
	}
}
func main()
{
	// Create tree objects
	let tree1: BinaryTree = BinaryTree();
	let tree2: 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   7
		-----------------------
	    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(7);
	//  Test Cases
	tree1.is_full_binary_tree();
	tree2.is_full_binary_tree();
}
main();

Output

 Tree Node :    6   7   8   1   11   5   6
 Is full binary tree

 Tree Node :    36   2   1   8   7   17   5   6
 Is not full binary tree
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment