Maximum width of a binary tree | C ++ program to calculate width of binary tree ; A binary tree node has data , pointer to left child and a pointer to right child ; A utility function to get height of a binary tree ; Function to get the maximum width of a binary tree ; Create an array that will store count of nodes at each level ; Fill the count array using preorder traversal ; Return the maximum value from count array ; A function that fills count array with count of nodes at every level of given binary tree ; Compute the " height " of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node . ; compute the height of each subtree ; use the larger one ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Return the maximum value from count array ; Driver code ; Constructed bunary tree is : 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; } ; int height ( node * node ) ; node * newNode ( int data ) ; void getMaxWidthRecur ( node * root , int count [ ] , int level ) ; int getMax ( int arr [ ] , int n ) ; int getMaxWidth ( node * root ) { int width ; int h = height ( root ) ; int * count = new int [ h ] ; int level = 0 ; getMaxWidthRecur ( root , count , level ) ; return getMax ( count , h ) ; } void getMaxWidthRecur ( node * root , int count [ ] , int level ) { if ( root ) { count [ level ] ++ ; getMaxWidthRecur ( root -> left , count , level + 1 ) ; getMaxWidthRecur ( root -> right , count , level + 1 ) ; } } int height ( node * node ) { if ( node == NULL ) return 0 ; else { int lHeight = height ( node -> left ) ; int rHeight = height ( node -> right ) ; return ( lHeight > rHeight ) ? ( lHeight + 1 ) : ( rHeight + 1 ) ; } } node * newNode ( int data ) { node * Node = new node ( ) ; Node -> data = data ; Node -> left = NULL ; Node -> right = NULL ; return ( Node ) ; } 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 ; } int main ( ) { 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 ) ; cout << " Maximum ▁ width ▁ is ▁ " << getMaxWidth ( root ) << endl ; return 0 ; }