Maximum width of a Binary Tree

Last Updated : 26 Mar, 2026

Given a binary tree, we need to find its maximum width. The width of a binary tree is defined as the maximum number of nodes present at any level of the tree.

Example:

Input:

Output: 3
Explanation: For the tree width is considered as number of nodes in that level ,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.
So the maximum width of the tree is 3.

Try it on GfG Practice

Table of Content

[Naive Approach] By Counting Nodes at Each Level
[Expected Approach 1] Using Level Order Traversal - O(n) Time and O(n) Space
[Expected Approach 2] Using Preorder Traversal - O(n) Time and O(n) Space

[Naive Approach] By Counting Nodes at Each Level

The idea is to first find the height of the tree, then for each level, count the number of nodes, and finally take the maximum of these counts as the width.

Steps to solve the problem:

Compute the height of the tree using recursion.
For each level from 1 to height:
Call a helper function that counts nodes at that level.
Update the maximum width after checking each level.

C++

#include <iostream>
#include<queue>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
    node (int d){
      this->data = d;
      this->left = this->right = NULL;
    }
};

/*Function prototypes*/
int getWidth(node* root, int level);
int height(node* node);

/* Function to get the maximum width of a binary tree*/
int getMaxWidth(node* root)
{
    int maxWidth = 0;
    int width;
    int h = height(root);
    int i;

    /* Get width of each level and compare
        the width with maximum width so far */
    for (i = 1; i <= h; i++) {
        width = getWidth(root, i);
        if (width > maxWidth)
            maxWidth = width;
    }

    return maxWidth;
}

/* Get width of a given level */
int getWidth(node* root, int level)
{
    if (root == NULL)
        return 0;
    if (level == 1)
        return 1;
    else if (level > 1)
        return getWidth(root->left, level - 1)
               + getWidth(root->right, level - 1);
}

/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(node* node)
{
    if (node == NULL)
        return 0;
    else {
        /* compute the height of each subtree */
        int lHeight = height(node->left);
        int rHeight = height(node->right);
        /* use the larger one */

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

/* Driver code*/
int main()
{
    node* root = new node(1);
    root->left = new node(2);
    root->right = new node(3);
    root->left->left = new node(4);
    root->left->right = new node(5);
    root->right->right = new node(8);
    root->right->right->left = new node(6);
    root->right->right->right = new node(7);

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

    // Function call
    cout << getMaxWidth(root)
         << endl;
    return 0;
}

C

// C program to calculate width of binary tree
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/*Function prototypes*/
int getWidth(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to get the maximum width of a binary tree*/
int getMaxWidth(struct node* root)
{
    int maxWidth = 0;
    int width;
    int h = height(root);
    int i;

    /* Get width of each level and compare
       the width with maximum width so far */
    for (i = 1; i <= h; i++) {
        width = getWidth(root, i);
        if (width > maxWidth)
            maxWidth = width;
    }

    return maxWidth;
}

/* Get width of a given level */
int getWidth(struct node* root, int level)
{

    if (root == NULL)
        return 0;

    if (level == 1)
        return 1;

    else if (level > 1)
        return getWidth(root->left, level - 1)
               + getWidth(root->right, level - 1);
}

/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
    if (node == NULL)
        return 0;
    else {
        /* compute the height of each subtree */
        int lHeight = height(node->left);
        int rHeight = height(node->right);
        /* use the larger one */

        return (lHeight > rHeight) ? (lHeight + 1)
                                   : (rHeight + 1);
    }
}
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
/* Driver code*/
int main()
{
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(8);
    root->right->right->left = newNode(6);
    root->right->right->right = newNode(7);

    /*
     Constructed binary tree is:
            1
          /  \
         2    3
       /  \     \
      4   5     8
                /  \
               6   7
    */
  
    // Function call
    printf("%d \n", getMaxWidth(root));
    getchar();
    return 0;
}

Java

class Node {
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    /* Function to get the maximum width of a binary tree*/
    int getMaxWidth(Node node)
    {
        int maxWidth = 0;
        int width;
        int h = height(node);
        int i;

        /* Get width of each level and compare
           the width with maximum width so far */
        for (i = 1; i <= h; i++) {
            width = getWidth(node, i);
            if (width > maxWidth)
                maxWidth = width;
        }

        return maxWidth;
    }

    /* Get width of a given level */
    int getWidth(Node node, int level)
    {
        if (node == null)
            return 0;

        if (level == 1)
            return 1;
        else if (level > 1)
            return getWidth(node.left, level - 1)
                + getWidth(node.right, level - 1);
        return 0;
    }

    /* UTILITY FUNCTIONS */

    /* Compute the "height" of a tree -- the number of
     nodes along the longest path from the root node
     down to the farthest leaf node.*/
    int height(Node node)
    {
        if (node == null)
            return 0;
        else {
            /* compute the height of each subtree */
            int lHeight = height(node.left);
            int rHeight = height(node.right);

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

    /* Driver code */
    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 Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.right = new Node(8);
        tree.root.right.right.left = new Node(6);
        tree.root.right.right.right = new Node(7);

        // Function call
        System.out.println(tree.getMaxWidth(tree.root));
    }
}

// This code has been contributed by Mayank Jaiswal

Python

# Python program to find the maximum width of
# binary tree using Level Order Traversal.

# A binary tree node


class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to get the maximum width of a binary tree


def getMaxWidth(root):
    maxWidth = 0
    h = height(root)
    # Get width of each level and compare the
    # width with maximum width so far
    for i in range(1, h+1):
        width = getWidth(root, i)
        if (width > maxWidth):
            maxWidth = width
    return maxWidth

# Get width of a given level


def getWidth(root, level):
    if root is None:
        return 0
    if level == 1:
        return 1
    elif level > 1:
        return (getWidth(root.left, level-1) +
                getWidth(root.right, level-1))

# UTILITY FUNCTIONS
# Compute the "height" of a tree -- the number of
# nodes along the longest path from the root node
# down to the farthest leaf node.


def height(node):
    if node is None:
        return 0
    else:

        # compute the height of each subtree
        lHeight = height(node.left)
        rHeight = height(node.right)

        # use the larger one
        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)


if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(8)
    root.right.right.left = Node(6)
    root.right.right.right = Node(7)
    print(getMaxWidth(root))

C#

// C# program to calculate width of binary tree
using System;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
public class Node {
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    public Node root;

    /* Function to get the maximum width of a binary tree*/
    public virtual int getMaxWidth(Node node)
    {
        int maxWidth = 0;
        int width;
        int h = height(node);
        int i;

        /* Get width of each level and compare
        the width with maximum width so far */
        for (i = 1; i <= h; i++) {
            width = getWidth(node, i);
            if (width > maxWidth) {
                maxWidth = width;
            }
        }

        return maxWidth;
    }

    /* Get width of a given level */
    public virtual int getWidth(Node node, int level)
    {
        if (node == null) {
            return 0;
        }

        if (level == 1) {
            return 1;
        }
        else if (level > 1) {
            return getWidth(node.left, level - 1)
                + getWidth(node.right, level - 1);
        }
        return 0;
    }

    /* UTILITY FUNCTIONS */

    /* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    public virtual int height(Node node)
    {
        if (node == null) {
            return 0;
        }
        else {
            /* compute the height of each subtree */
            int lHeight = height(node.left);
            int rHeight = height(node.right);

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

    /* Driver code */
    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 Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.right = new Node(8);
        tree.root.right.right.left = new Node(6);
        tree.root.right.right.right = new Node(7);
 
        // Function call
        Console.WriteLine(""
                          + tree.getMaxWidth(tree.root));
    }
}

JavaScript

Output

Time Complexity: O(N²) in the worst case.
Auxiliary Space: O(h) The only extra space used is the recursion stack, which in worst case is equal to the height of the tree O(h).

[Expected Approach 1] Using Level Order Traversal - O(n) Time and O(n) Space

The idea is to use level order traversal (BFS) and count the number of nodes at each level. The maximum count across all levels will be the width of the tree.

Steps to solve the problem:

Use a queue to perform level order traversal.
For each level, get the size of the queue (this gives the number of nodes at that level).
Update the answer with the maximum size encountered so far.
Push the children of each node into the queue and continue until the tree is fully traversed.

C++

// A queue based C++ program to find maximum width
// of a Binary Tree
#include <iostream>
#include<queue>
using namespace std;

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    Node(int d)
    {
        this->data = d;
        this->left = this->right = NULL;
    }
};

// Function to find the maximum width of the tree
// using level order traversal
int maxWidth(struct Node* root)
{
    // Base case
    if (root == NULL)
        return 0;

    // Initialize result
    int result = 0;

    // Do Level order traversal keeping track of number
    // of nodes at every level.
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        
        // Get the size of queue when the level order
        // traversal for one level finishes
        int count = q.size();

        // Update the maximum node count value
        result = max(count, result);

        // Iterate for all the nodes in the queue currently
        while (count--) {
            // Dequeue an node from queue
            Node* temp = q.front();
            q.pop();

            // Enqueue left and right children of
            // dequeued node
            if (temp->left != NULL)
                q.push(temp->left);
            if (temp->right != NULL)
                q.push(temp->right);
        }
    }

    return result;
}

// Driver code
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(8);
    root->right->right->left = new Node(6);
    root->right->right->right = new Node(7);

    /*   Constructed Binary tree is:
                 1
               /   \
              2      3
             /  \     \
            4    5     8
                     /   \
                    6     7    */
    cout << maxWidth(root) << endl;
    return 0;
}

Java

// Java program to calculate maximum width
// of a binary tree using queue
import java.util.LinkedList;
import java.util.Queue;

public class maxwidthusingqueue 
{
    /* A binary tree node has data, pointer to
       left child and a pointer to right child */
    static class node 
    {
        int data;
        node left, right;

        public node(int data) { this.data = data; }
    }

    // Function to find the maximum width of
    // the tree using level order traversal
    static int maxwidth(node root)
    {
        // Base case
        if (root == null)
            return 0;

        // Initialize result
        int maxwidth = 0;

        // Do Level order traversal keeping
        // track of number of nodes at every level
        Queue<node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) 
        {
            // Get the size of queue when the level order
            // traversal for one level finishes
            int count = q.size();

            // Update the maximum node count value
            maxwidth = Math.max(maxwidth, count);

            // Iterate for all the nodes in
            // the queue currently
            while (count-- > 0) {
                // Dequeue an node from queue
                node temp = q.remove();

                // Enqueue left and right children
                // of dequeued node
                if (temp.left != null)
                {
                    q.add(temp.left);
                }
                if (temp.right != null)
                {
                    q.add(temp.right);
                }
            }
        }
        return maxwidth;
    }
  
    
    // Function call
    public static void main(String[] args)
    {
        node root = new node(1);
        root.left = new node(2);
        root.right = new node(3);
        root.left.left = new node(4);
        root.left.right = new node(5);
        root.right.right = new node(8);
        root.right.right.left = new node(6);
        root.right.right.right = new node(7);

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

        System.out.println( maxwidth(root));
    }
}

Python

# Python program to find the maximum width of binary
# tree using Level Order Traversal with queue.

from _collections import deque

# A binary tree node
class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to get the maximum width of a binary tree


def getMaxWidth(root):
    # base case
    if root is None:
        return 0
    q = deque()
    maxWidth = 0

    q.append(root)

    while q:
        # Get the size of queue when the level order
        # traversal for one level finishes
        count = len(q)

        # Update the maximum node count value
        maxWidth = max(count, maxWidth)

        while (count is not 0):
            count = count-1
            temp = q.popleft()
            if temp.left is not None:
                q.append(temp.left)

            if temp.right is not None:
                q.append(temp.right)

    return maxWidth

if __name__=="__main__":
    # Driver program to test above function
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(8)
    root.right.right.left = Node(6)
    root.right.right.right = Node(7)
    
    """
    Constructed binary tree is:
           1
          / \
         2   3
        / \    \
       4   5   8 
              / \
             6   7
    """
    print(getMaxWidth(root)))

C#

// C# program to calculate maximum width
// of a binary tree using queue
using System;
using System.Collections.Generic;

public class maxwidthusingqueue 
{
    /* A binary tree node has data, pointer to
    left child and a pointer to right child */
    public class node 
    {
        public int data;
        public node left, right;

        public node(int data) { this.data = data; }
    }

    // Function to find the maximum width of
    // the tree using level order traversal
    static int maxwidth(node root)
    {
        // Base case
        if (root == null)
            return 0;

        // Initialize result
        int maxwidth = 0;

        // Do Level order traversal keeping
        // track of number of nodes at every level
        Queue<node> q = new Queue<node>();
        q.Enqueue(root);
        while (q.Count != 0) 
        {
            // Get the size of queue when the level order
            // traversal for one level finishes
            int count = q.Count;

            // Update the maximum node count value
            maxwidth = Math.Max(maxwidth, count);

            // Iterate for all the nodes in
            // the queue currently
            while (count-- > 0) {
                // Dequeue an node from queue
                node temp = q.Dequeue();

                // Enqueue left and right children
                // of dequeued node
                if (temp.left != null) 
                {
                    q.Enqueue(temp.left);
                }
                if (temp.right != null) 
                {
                    q.Enqueue(temp.right);
                }
            }
        }
        return maxwidth;
    }
    public static void Main(String[] args)
    {
        node root = new node(1);
        root.left = new node(2);
        root.right = new node(3);
        root.left.left = new node(4);
        root.left.right = new node(5);
        root.right.right = new node(8);
        root.right.right.left = new node(6);
        root.right.right.right = new node(7);

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

        Console.WriteLine(""
                          + maxwidth(root));
    }
}

JavaScript

// JavaScript program to calculate maximum width
// of a binary tree using queue

class node {
    constructor(data) {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}

// Function to find the maximum width of
// the tree using level order traversal
function maxwidth(root) {
    // Base case
    if (root == null)
        return 0;

    // Initialize result
    let maxwidth = 0;

    // Do Level order traversal keeping
    // track of number of nodes at every level
    let q = [];
    q.push(root);
    while (q.length > 0) {
        // Get the size of queue when the level order
        // traversal for one level finishes
        let count = q.length;

        // Update the maximum node count value
        maxwidth = Math.max(maxwidth, count);

        // Iterate for all the nodes in
        // the queue currently
        while (count-- > 0) {
            // Dequeue a node from queue
            let temp = q.shift();

            // Enqueue left and right children
            // of dequeued node
            if (temp.left != null) {
                q.push(temp.left);
            }
            if (temp.right != null) {
                q.push(temp.right);
            }
        }
    }
    return maxwidth;
}

// Driver code
let root = new node(1);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(5);
root.right.right = new node(8);
root.right.right.left = new node(6);
root.right.right.right = new node(7);

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

console.log(maxwidth(root));

Output

[Expected Approach 2] Using Preorder Traversal - O(n) Time and O(n) Space

The idea behind this approach is to find the level of a node and increment the count of nodes for that level. The number of nodes present at a certain level is the width of that level.

Follow the steps mentioned below to implement the approach:

Create a temporary array count of size equal to the height of the tree.
Initialize all values in count as 0.
Traverse the tree using preorder traversal and fill the entries in count so that
The count array contains the count of nodes at each level of the Binary Tree.
The level with the maximum number of nodes has the maximum width.
Return the value of that level.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Tree node structure
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

// Preorder traversal to count nodes at each level
void preorder(Node* root, int level, vector<int>& count) {
    if (root == NULL) return;

    // If this is the first node of this level, extend the vector
    if (level == count.size()) {
        count.push_back(0);
    }

    // Increase count of nodes at this level
    count[level]++;

    // Recurse for left and right subtrees
    preorder(root->left, level + 1, count);
    preorder(root->right, level + 1, count);
}

// Function to get maximum width
int getMaxWidth(Node* root) {
    vector<int> count;
    preorder(root, 0, count);

    int maxWidth = 0;
    for (int c : count) {
        maxWidth = max(maxWidth, c);
    }
    return maxWidth;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(8);
    root->right->right->left = new Node(6);
    root->right->right->right = new Node(7);

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

    cout << getMaxWidth(root) << endl;
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

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

// Create a new node
struct Node* newNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = val;
    node->left = node->right = NULL;
    return node;
}

// Preorder traversal to count nodes at each level
void preorder(struct Node* root, int level, int count[], int* maxLevel) {
    if (root == NULL) return;

    // If this is the first node of this level, extend count
    if (level > *maxLevel) {
        *maxLevel = level;
    }

    // Increase count of nodes at this level
    count[level]++;

    // Recurse for left and right subtrees
    preorder(root->left, level + 1, count, maxLevel);
    preorder(root->right, level + 1, count, maxLevel);
}

// Function to get maximum width
int getMaxWidth(struct Node* root) {
    int count[1000] = {0}; // assume tree won't have more than 1000 levels
    int maxLevel = -1;
    preorder(root, 0, count, &maxLevel);

    int maxWidth = 0;
    for (int i = 0; i <= maxLevel; i++) {
        if (count[i] > maxWidth)
            maxWidth = count[i];
    }
    return maxWidth;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(8);
    root->right->right->left = newNode(6);
    root->right->right->right = newNode(7);

    printf("%d\n", getMaxWidth(root));
    return 0;
}

Java

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

public class Main {

    // Preorder traversal to count nodes at each level
    static void preorder(Node root, int level, List<Integer> count) {
        if (root == null) return;

        // If this is the first node of this level, extend the list
        if (level == count.size()) {
            count.add(0);
        }

        // Increase count of nodes at this level
        count.set(level, count.get(level) + 1);

        // Recurse for left and right subtrees
        preorder(root.left, level + 1, count);
        preorder(root.right, level + 1, count);
    }

    // Function to get maximum width
    static int getMaxWidth(Node root) {
        List<Integer> count = new ArrayList<>();
        preorder(root, 0, count);

        int maxWidth = 0;
        for (int c : count) {
            maxWidth = Math.max(maxWidth, c);
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(8);
        root.right.right.left = new Node(6);
        root.right.right.right = new Node(7);

        System.out.println(getMaxWidth(root));
    }
}

Python

# Tree node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

# Preorder traversal to count nodes at each level
def preorder(root, level, count):
    if root is None:
        return

    # If this is the first node of this level, extend the list
    if level == len(count):
        count.append(0)

    # Increase count of nodes at this level
    count[level] += 1

    # Recurse for left and right subtrees
    preorder(root.left, level + 1, count)
    preorder(root.right, level + 1, count)

# Function to get maximum width
def getMaxWidth(root):
    count = []
    preorder(root, 0, count)
    return max(count) if count else 0

if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(8)
    root.right.right.left = Node(6)
    root.right.right.right = Node(7)
    
    print(getMaxWidth(root))

C#

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class Program {

    // Preorder traversal to count nodes at each level
    static void Preorder(Node root, int level, List<int> count) {
        if (root == null) return;

        // If this is the first node of this level, extend the list
        if (level == count.Count) {
            count.Add(0);
        }

        // Increase count of nodes at this level
        count[level]++;

        // Recurse for left and right subtrees
        Preorder(root.left, level + 1, count);
        Preorder(root.right, level + 1, count);
    }

    // Function to get maximum width
    static int GetMaxWidth(Node root) {
        List<int> count = new List<int>();
        Preorder(root, 0, count);

        int maxWidth = 0;
        foreach (int c in count) {
            maxWidth = Math.Max(maxWidth, c);
        }
        return maxWidth;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(8);
        root.right.right.left = new Node(6);
        root.right.right.right = new Node(7);

        Console.WriteLine(GetMaxWidth(root));
    }
}

JavaScript

// Tree node structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Preorder traversal to count nodes at each level
function preorder(root, level, count) {
    if (root === null) return;

    // If this is the first node of this level, extend the array
    if (level === count.length) {
        count.push(0);
    }

    // Increase count of nodes at this level
    count[level]++;

    // Recurse for left and right subtrees
    preorder(root.left, level + 1, count);
    preorder(root.right, level + 1, count);
}

// Function to get maximum width
function getMaxWidth(root) {
    let count = [];
    preorder(root, 0, count);

    let maxWidth = 0;
    for (let c of count) {
        maxWidth = Math.max(maxWidth, c);
    }
    return maxWidth;
}

// Driver code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);

console.log(getMaxWidth(root));

Output

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem