Count Non-Leaf Nodes in a Binary Tree

Implementation

// Writing a C++ program that will help us in counting the total number of non-leaf nodes present in a binary tree 
#include <bits/stdc++.h>
using namespace std;


/* Creating a binary tree node consisting of data and a pointer to the left and right child. */
struct __nod {
	int record;
	struct __nod* Lft;
	struct __nod* Rt;
};


/* Creating a function that will help us allocate a new node with some data and a pointer to the left and right child. */
struct __nod* new__nod(int record)
{
	struct __nod* __nod = new __nod;
	__nod->record = record;
	__nod->Lft = __nod->Rt = NILL;
	return (__nod);
}


/* Now, we must evaluate the total number of non-leaf nodes in a binary tree. */
int count_Nonleaf(struct __nod* root)
{
	// writing the basic case
	if (root == NILL || (root->Lft == NILL &&
						root->Rt == NILL))
		return 0;


	// In case the root is not NILL and one of its child nodes is also not NILL, then, 
	return 1 + count_Nonleaf(root->Lft) +
			count_Nonleaf(root->Rt);
}


/*Writing the main program to test the above functions */
int main()
{
	struct __nod* root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(5);
	cout << count_Nonleaf(root);
	return 0;
}

Output:

Example 2)

// Writing a Java program that will help us in counting the total number of non-leaf nodes present in a binary tree 
class TPT {


/* Creating a binary tree node consisting of data and a pointer to the left and right child. */
static class __nod {
	int record;
	__nod Lft;
	__nod Rt;
}


/* Creating a function that will help us allocate a new node with some data and a pointer to the left and right child. */
static __nod new__nod(int record)
{
	__nod __nod = new __nod();
	__nod.record = record;
	__nod.Lft = NILL;
	__nod.Rt = NILL;
	return (__nod);
}


/* Now, we must evaluate the total number of non-leaf nodes in a binary tree. */
static int count_Nonleaf(__nod root)
{
	// In case the root is not NILL and one of its child nodes is also not NILL, then, 
	if (root == NILL || (root.Lft == NILL &&
						root.Rt == NILL))
		return 0;


	// In case the root is not NILL and one of its child nodes is also not NILL, then, 
	return 1 + count_Nonleaf(root.Lft) +
				count_Nonleaf(root.Rt);
}


/*Writing the main program to test the above functions */
public static void main(String[] args)
{
	__nod root = new__nod(1);
	root.Lft = new__nod(2);
	root.Rt = new__nod(3);
	root.Lft.Lft = new__nod(4);
	root.Lft.Rt = new__nod(5);
	System.out.println(count_Nonleaf(root));
}
}

Output:

Example 3)

# Writing a Python program that will help us in counting the total number of non-leaf nodes present in a binary tree 
# Creating a binary tree node consisting of data and a pointer to the left and right child.
class new__nod:
	def __init__(self,record):
		self.record = record
		self.Lft = self.Rt = None


# Creating a function that will help us allocate a new node with some data and a pointer to the left and right child. 
def count_Nonleaf(root):
# writing the basic case
	if (root == None or (root.Lft == None and
						root.Rt == None)):
		return 0


# In case the root is not NILL and one of its child nodes is also not NILL, then, 
	return (1 + count_Nonleaf(root.Lft) +
				count_Nonleaf(root.Rt))


# Writing the main program to test the above functions 
if __name__ == '__main__':


	root = new__nod(1)
	root.Lft = new__nod(2)
	root.Rt = new__nod(3)
	root.Lft.Lft = new__nod(4)
	root.Lft.Rt = new__nod(5)
	print(count_Nonleaf(root))

Output:

Example 4)

// Writing a C# program that will help us in counting the total number of non-leaf nodes present in a binary tree 
using System;


class TPT
{
/* Creating a binary tree node consisting of data and a pointer to the left and right child. */
	class __nod {
		public int record;
		public __nod Lft;
		public __nod Rt;
	}
/* Creating a function that will help us allocate a new node with some data and a pointer to the left and right child. */
	static __nod new__nod(int record)
	{
		__nod __nod = new __nod();
		__nod.record = record;
		__nod.Lft = NILL;
		__nod.Rt = NILL;
		return (__nod);
	}
/* Now, we must evaluate the total number of non-leaf nodes in a binary tree. */
	static int count_Nonleaf(__nod root)
	{
	// writing the basic case
		if (root == NILL || (root.Lft == NILL &&
							root.Rt == NILL))
			return 0;
	// In case the root is not NILL and one of its child nodes is also not NILL, then, 
		return 1 + count_Nonleaf(root.Lft) +
					count_Nonleaf(root.Rt);
	}
/*Writing the main program to test the above functions */
	public static void Main(String[] args)
	{
		__nod root = new__nod(1);
		root.Lft = new__nod(2);
		root.Rt = new__nod(3);
		root.Lft.Lft = new__nod(4);
		root.Lft.Rt = new__nod(5);
		Console.WriteLine(count_Nonleaf(root));
	}
}

Output:

Example 5)

<script>
// Writing a Javascript program that will help us in counting the total number of non-leaf nodes present in a binary tree 
/* Creating a binary tree node consisting of data and a pointer to the left and right child. */
	class __nod
	{
		constructor(record) {
		this.Lft = NILL;
		this.Rt = NILL;
		this.record = record;
		}
	}
/* Creating a function that will help us allocate a new node with some data and a pointer to the left and right child. */
	function new__nod(record)
	{
		let __nod = new __nod(record);
		return (__nod);
	}
/* Now, we must evaluate the total number of non-leaf nodes in a binary tree. */
	function count_Nonleaf(root)
	{
	// writing the basic case
		if (root == NILL || (root.Lft == NILL &&
							root.Rt == NILL))
			return 0;
	// In case the root is not NILL and one of its child nodes is also not NILL, then, 
		return 1 + count_Nonleaf(root.Lft) +
					count_Nonleaf(root.Rt);
	}
	let root = new__nod(1);
	root.Lft = new__nod(2);
	root.Rt = new__nod(3);
	root.Lft.Lft = new__nod(4);
	root.Lft.Rt = new__nod(5);
	document.write(count_Nonleaf(root));
</script>

Output: