# 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: 