Maximum width Using Preorder Traversal

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.

For traversal we can here use the preorder traversal.

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.

Below is the implementation of the above approach.

C++

// C++ program to calculate width of binary tree
#include <bits/stdc++.h>
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;
    }
};

// A utility function to get
// height of a binary tree
int height(node* node);

// A utility function that returns
// maximum value in arr[] of size n
int getMax(int arr[], int n);

// A function that fills count array
// with count of nodes at every
// level of given binary tree
void getMaxWidthRecur(node* root, int count[], int level);

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

    // Create an array that will
    // store count of nodes at each level
    int* count = new int[h];

    int level = 0;

    // Fill the count array using preorder traversal
    getMaxWidthRecur(root, count, level);

    // Return the maximum value from count array
    return getMax(count, h);
}

// A function that fills count array
// with count of nodes at every
// level of given binary tree
void getMaxWidthRecur(node* root, 
                      int count[], int level)
{
    if (root) {
        count[level]++;
        getMaxWidthRecur(root->left, count, level + 1);
        getMaxWidthRecur(root->right, count, 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);
    }
}

// Return the maximum value from count array
int getMax(int arr[], int n)
{
    int max = arr[0];
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    return max;
}

/* 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);

    cout << "Maximum width is " << getMaxWidth(root)
         << endl;
    return 0;
}

// This is code is contributed by rathbhupendra

// 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;
};

// A utility function to get height of a binary tree
int height(struct node* node);

// A utility function to allocate a new node with given data
struct node* newNode(int data);

// A utility function that returns maximum value in arr[] of
// size n
int getMax(int arr[], int n);

// A function that fills count array with count of nodes at
// every level of given binary tree
void getMaxWidthRecur(struct node* root, int count[],
                      int level);

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

    // Create an array that will store count of nodes at
    // each level
    int* count = (int*)calloc(sizeof(int), h);

    int level = 0;

    // Fill the count array using preorder traversal
    getMaxWidthRecur(root, count, level);

    // Return the maximum value from count array
    return getMax(count, h);
}

// A function that fills count array with count of nodes at
// every level of given binary tree
void getMaxWidthRecur(struct node* root, int count[],
                      int level)
{
    if (root) {
        count[level]++;
        getMaxWidthRecur(root->left, count, level + 1);
        getMaxWidthRecur(root->right, count, 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);
}

// Return the maximum value from count array
int getMax(int arr[], int n)
{
    int max = arr[0];
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    return max;
}

/* Driver program to test above functions*/
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
    */
    printf("Maximum width is %d \n", getMaxWidth(root));
    getchar();
    return 0;
}

Java

// Java program to calculate width of binary tree

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
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 width;
        int h = height(node);

        // Create an array that will store count of nodes at
        // each level
        int count[] = new int[10];

        int level = 0;

        // Fill the count array using preorder traversal
        getMaxWidthRecur(node, count, level);

        // Return the maximum value from count array
        return getMax(count, h);
    }

    // A function that fills count array with count of nodes
    // at every level of given binary tree
    void getMaxWidthRecur(Node node, int count[], int level)
    {
        if (node != null) {
            count[level]++;
            getMaxWidthRecur(node.left, count, level + 1);
            getMaxWidthRecur(node.right, count, 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);
        }
    }

    // Return the maximum value from count array
    int getMax(int arr[], int n)
    {
        int max = arr[0];
        int i;
        for (i = 0; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        return max;
    }

    /* Driver program to test 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 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);

        System.out.println("Maximum width is "
                           + tree.getMaxWidth(tree.root));
    }
}

// This code has been contributed by Mayank Jaiswal

Python

# Python program to find the maximum width of 
# binary tree using Preorder 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):
    h = height(root)
    # Create an array that will store count of nodes at each level
    count = [0] * h

    level = 0
    # Fill the count array using preorder traversal
    getMaxWidthRecur(root, count, level)

    # Return the maximum value from count array
    return getMax(count, h)

# A function that fills count array with count of nodes at every
# level of given binary tree


def getMaxWidthRecur(root, count, level):
    if root is not None:
        count[level] += 1
        getMaxWidthRecur(root.left, count, level+1)
        getMaxWidthRecur(root.right, count, 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)

# Return the maximum value from count array


def getMax(count, n):
    max = count[0]
    for i in range(1, n):
        if (count[i] > max):
            max = count[i]
    return max


# 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 ("Maximum width is %d" % (getMaxWidth(root)))

# This code is contributed by Naveen Aili

// 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 
{
    Node root;

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

        // Create an array that will store
        // count of nodes at each level
        int[] count = new int[10];

        int level = 0;

        // Fill the count array using preorder traversal
        getMaxWidthRecur(node, count, level);

        // Return the maximum value from count array
        return getMax(count, h);
    }

    // A function that fills count
    // array with count of nodes at every
    // level of given binary tree
    void getMaxWidthRecur(Node node, int[] count, int level)
    {
        if (node != null) 
        {
            count[level]++;
            getMaxWidthRecur(node.left, count, level + 1);
            getMaxWidthRecur(node.right, count, 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);
        }
    }

    // Return the maximum value from count array
    int getMax(int[] arr, int n)
    {
        int max = arr[0];
        int i;
        for (i = 0; i < n; i++) 
        {
            if (arr[i] > max)
                max = arr[i];
        }
        return max;
    }

    /* Driver program to test above functions */
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        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);

        Console.WriteLine("Maximum width is "
                          + tree.getMaxWidth(tree.root));
    }
}

// This code is contributed Rajput-Ji

Javascript

<script>
// javascript program to calculate width of binary tree

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}
var root;

    /* Function to get the maximum width of a binary tree*/
    function getMaxWidth(node)
    {
        var width;
        var h = height(node);

        // Create an array that will store count of nodes at
        // each level
        var count = Array(10).fill(0);

        var level = 0;

        // Fill the count array using preorder traversal
        getMaxWidthRecur(node, count, level);

        // Return the maximum value from count array
        return getMax(count, h);
    }

    // A function that fills count array with count of nodes
    // at every level of given binary tree
    function getMaxWidthRecur(node , count , level)
    {
        if (node != null) {
            count[level]++;
            getMaxWidthRecur(node.left, count, level + 1);
            getMaxWidthRecur(node.right, count, level + 1);
        }
    }

    /* UTILITY FUNCTIONS */

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

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

    // Return the maximum value from count array
    function getMax(arr , n)
    {
        var max = arr[0];
        var i;
        for (i = 0; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        return max;
    }

    /* Driver program to test above functions */
    

        /*
        Constructed binary tree is:
              1
            /  \
           2    3
          / \    \
         4   5    8
                 / \
                6   7 */
        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);

        document.write("Maximum width is "
                           + getMaxWidth(root));

// This code is contributed by Rajput-Ji
</script>

Output

Maximum width is 3

Time Complexity: O(N)
Auxiliary Space: O(h) where h is the height of the tree.

Thanks to Raja and Jagdish for suggesting this method.
Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.

Maximum width of a Binary Tree

Given a binary tree, the task is to find the maximum width of the given tree. The width of a tree is the maximum of the widths of all levels. Before solving the problem first, let us understand what we have to do. Binary trees are one of the most common types of trees in computer science. They are also called “balanced” trees because all of their nodes have an equal number of children. In this case, we will focus on finding the maximum value of W, which is the width of a binary tree. For example, given a binary tree with root node A, which has two children B and C, where B has two children D and E and C has one child F, the maximum width is 3.
The maximum width of a binary tree is the number of nodes at any level. In other words, it is the minimum number of nodes in a tree that can be traversed before you need to make a choice on which node to visit next.

Example:

Input:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Output: 3
Explanation: For the above tree,
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.

Maximum width Using Preorder Traversal

Maximum width of a Binary Tree

Categories

Contact US

Maximum width Using Preorder Traversal

Maximum width of a Binary Tree

Similar Reads

Categories

Contact US