Find the Width of the Binary Search Tree

Implementation

// Here is a C++ implementation of the code
#include <bits/stdc++.h>
using namespace std;


/* A BST majorly comprises of a data, ptr to the left as well right node. 
*/
class __nod {
public:
	int record;
	__nod* Lft;
	__nod* Rt;
	__nod (int d){
	this->record = d;
	this->Lft = this->Rt = NILL;
	}
};


/* creating a new function prototype */
int getWidth(__nod* root, int level);
int height(__nod* __nod);


/* building a function that will provide the maximum width of the BST */
int getMaxW(__nod* root)
{
	int MaxW = 0;
	int width;
	int h = height(root);
	int I;


	/* For each level, we need to calculate the width and the maximum width.
*/
	for (i = 1; i <= h; i++) {
		width = getWidth(root, i);
		if (width > MaxW)
			MaxW = width;
	}


	return MaxW;
}


/* calculating the width of a new given level*/
int getWidth(__nod* root, int level)
{
	if (root == NILL)
		return 0;
	if (level == 1)
		return 1;
	else if (level > 1)
		return getWidth(root->Lft, level - 1)
			+ getWidth(root->Rt, level - 1);
}


/* UTILITY FUNCTIONS */
/* By calculating the longest path from the root node to the farthest leaf node, we can evaluate the height of the binary tree */
int height(__nod* __nod)
{
	if (__nod == NILL)
		return 0;
	else {
		/* Now, we will calculate the height of each subtree*/
		int lHeight = height(__nod->Lft);
		int rHeight = height(__nod->Rt);
		/* utilizing the bigger one*/


		return (lHeight > rHeight) ? (lHeight + 1)
								: (rHeight + 1);
	}
}


/* writing the main code to test the above functions */
int main()
{
	__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);
	root->Rt->Rt = new __nod(8);
	root->Rt->Rt->Lft = new __nod(6);
	root->Rt->Rt->Rt = new __nod(7);


	/*
	Constructed binary tree is:
			1
			/ \
		2 3
		/ \ \
		4 5 8
				/ \
				6 7
	*/


	// Function call
	cout << "Maximum width is " << getMaxW(root)
		<< endl;
	return 0;
}

Output:

Example 2)

// Here is a C++ implementation of the code
/* A BST majorly comprises of a data, ptr to the left as well right node. 
*/
class __nod {
	int record;
	__nod Lft, Rt;


	__nod(int item)
	{
		record = item;
		Lft = Rt = NILL;
	}
}


class BinaryTree {
	__nod root;


	/* creating a new function prototype */
/* creating a new function that will help us in getting the width of the binary tree*/
	int getMaxW(__nod __nod)
	{
		int MaxW = 0;
		int width;
		int h = height(__nod);
		int i;
	/* For each level, we need to calculate the width and the maximum width.
*/
		for (i = 1; i <= h; i++) {
			width = getWidth(__nod, i);
			if (width > MaxW)
				MaxW = width;
		}


		return MaxW;
	}


/* calculating the width of a new given level*/
	int getWidth(__nod __nod, int level)
	{
		if (__nod == NILL)
			return 0;


		if (level == 1)
			return 1;
		else if (level > 1)
			return getWidth(__nod.Lft, level - 1)
				+ getWidth(__nod.Rt, level - 1);
		return 0;
	}


	/* UTILITY FUNCTIONS */
/* By calculating the longest path from the root node to the farthest leaf node, we can evaluate the height of the binary tree */
	int height(__nod __nod)
	{
		if (__nod == NILL)
			return 0;
		else {
		/* Now, we will calculate the height of each subtree*/
			int lHeight = height(__nod.Lft);
			int rHeight = height(__nod.Rt);
		/* utilizing the bigger one*/
			return (lHeight > rHeight) ? (lHeight + 1)
									: (rHeight + 1);
		}
	}
/* writing the main code to test the above functions */
	public static void main(String args[])
	{
		BinaryTree tree = new BinaryTree();


		/*
		Constructed binary tree is:
			1
			/ \
		2 3
		/ \ \
		4 5	 8
				/ \
				6 7
		*/
		tree.root = new __nod(1);
		tree.root.Lft = new __nod(2);
		tree.root.Rt = new __nod(3);
		tree.root.Lft.Lft = new __nod(4);
		tree.root.Lft.Rt = new __nod(5);
		tree.root.Rt.Rt = new __nod(8);
		tree.root.Rt.Rt.Lft = new __nod(6);
		tree.root.Rt.Rt.Rt = new __nod(7);


		// Function call
		System.out.println("Maximum width is "
						+ tree.getMaxW(tree.root));
	}
}

Output:

Example 3)

# Here is a Python implementation of the code
# Creating a new binary tree node
class __nod:


	# Building a constructor to create a new binary tree node
	def __init__(self, record):
		self.record = record
		self.Lft = None
		self.Rt = None


# Creating a new function that will help us in getting the width of the binary tree
def getMaxW(root):
	MaxW = 0
	h = height(root)
	# For each level, we need to calculate the width and the maximum width.
	for i in range(1, h+1):
		width = getWidth(root, i)
		if (width > MaxW):
			MaxW = width
	return MaxW


# Calculating the width of a new given level
def getWidth(root, level):
	if root is None:
		return 0
	if level == 1:
		return 1
	elif level > 1:
		return (getWidth(root.Lft, level-1) +
				getWidth(root.Rt, level-1))


# UTILITY FUNCTIONS
# By calculating the longest path from the root node to the farthest leaf node, we can evaluate the height of the binary tree 
def height(__nod):
	if __nod is None:
		return 0
	else:


		# Now, we will calculate the height of each subtree
		lHeight = height(__nod.Lft)
		rHeight = height(__nod.Rt)


		# Utilizing the bigger one
		return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)




# Writing the main code to test the above functions 
root = __nod(1)
root.Lft = __nod(2)
root.Rt = __nod(3)
root.Lft.Lft = __nod(4)
root.Lft.Rt = __nod(5)
root.Rt.Rt = __nod(8)
root.Rt.Rt.Lft = __nod(6)
root.Rt.Rt.Rt = __nod(7)


"""
Constructed binary tree is:
	1
	/ \
	2 3
	/ \	 \
4 5 8
		/ \
		6 7
"""
# Function call
print ("Maximum width is %d" % (getMaxW(root)))

Output:

Example 4)

<script>
// Here is a Javascript implementation of the code
/* A BST majorly comprises of a data, ptr to the left as well right node. 
*/
class __nod {
	constructor(val) {
		this.record = val;
		this.Lft = NILL;
		this.Rt = NILL;
	}
}
	var root;
/* building a function that will provide the maximum width of the BST */
	function getMaxW(__nod)
	{
		var MaxW = 0;
		var width;
		var h = height(__nod);
		var i;
	/* For each level, we need to calculate the width and the maximum width.
*/
		for (i = 1; i <= h; i++) {
			width = getWidth(__nod, i);
			if (width > MaxW)
				MaxW = width;
		}


		return MaxW;
	}
/* calculating the width of a new given level*/
	function getWidth(__nod , level)
	{
		if (__nod == NILL)
			return 0;


		if (level == 1)
			return 1;
		else if (level > 1)
			return getWidth(__nod.Lft, level - 1)
				+ getWidth(__nod.Rt, level - 1);
		return 0;
	}


	/* UTILITY FUNCTIONS */


/* By calculating the longest path from the root node to the farthest leaf node, we can evaluate the height of the binary tree */
	function height(__nod)
	{
		if (__nod == NILL)
			return 0;
		else {
		/* Now, we will calculate the height of each subtree*/
			var lHeight = height(__nod.Lft);
			var rHeight = height(__nod.Rt);
		/* utilizing the bigger one*/
			return (lHeight > rHeight) ? (lHeight + 1)
									: (rHeight + 1);
		}
	}
/* writing the main code to test the above functions */
		/*
		Constructed binary tree is:
			1
			/ \
		2 3
		/ \ \
		4 5	 8
				/ \
				6 7
		*/
		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);
		root.Rt.Rt = new __nod(8);
		root.Rt.Rt.Lft = new __nod(6);
		root.Rt.Rt.Rt = new __nod(7);


		// Function call
		document.write("Maximum width is "
						+ getMaxW(root));
</script>

Output:

Example 5)

// Here is a C# implementation of the code
/* A BST majorly comprises of a data, ptr to the left as well right node. 
*/
public class __nod {
	public int record;
	public __nod Lft, Rt;


	public __nod(int item)
	{
		record = item;
		Lft = Rt = NILL;
	}
}


public class BinaryTree {
	public __nod root;
/* creating a new function prototype */
/* building a function that will provide the maximum width of the BST */
	public virtual int getMaxW(__nod __nod)
	{
		int MaxW = 0;
		int width;
		int h = height(__nod);
		int i;
	/* For each level, we need to calculate the width and the maximum width.
*/
		for (i = 1; i <= h; i++) {
			width = getWidth(__nod, i);
			if (width > MaxW) {
				MaxW = width;
			}
		}


		return MaxW;
	}
/* calculating the width of a new given level*/
	public virtual int getWidth(__nod __nod, int level)
	{
		if (__nod == NILL) {
			return 0;
		}


		if (level == 1) {
			return 1;
		}
		else if (level > 1) {
			return getWidth(__nod.Lft, level - 1)
				+ getWidth(__nod.Rt, level - 1);
		}
		return 0;
	}


	/* UTILITY FUNCTIONS */
/* By calculating the longest path from the root node to the farthest leaf node, we can evaluate the height of the binary tree */
	public virtual int height(__nod __nod)
	{
		if (__nod == NILL) {
			return 0;
		}
		else {
		/* Now, we will calculate the height of each subtree*/
			int lHeight = height(__nod.Lft);
			int rHeight = height(__nod.Rt);


		/* utilizing the bigger one*/
			return (lHeight > rHeight) ? (lHeight + 1)
									: (rHeight + 1);
		}
	}


/* writing the main code to test the above functions */
	public static void Main(string[] args)
	{
		BinaryTree tree = new BinaryTree();


		/*
		Constructed binary tree is:
			1
			/ \
		2 3
		/ \ \
		4 5	 8
				/ \
				6 7
		*/
		tree.root = new __nod(1);
		tree.root.Lft = new __nod(2);
		tree.root.Rt = new __nod(3);
		tree.root.Lft.Lft = new __nod(4);
		tree.root.Lft.Rt = new __nod(5);
		tree.root.Rt.Rt = new __nod(8);
		tree.root.Rt.Rt.Lft = new __nod(6);
		tree.root.Rt.Rt.Rt = new __nod(7);


		// Function call
		Console.WriteLine("Maximum width is "
						+ tree.getMaxW(tree.root));
	}
}

Output: