The Width of a Binary Tree

The width of a binary tree is defined as the maximum number of nodes of the same level. Assume a binary tree is like

        1

     /    \

   2       3

 /   \    /  \

4    5   6    7

Then the width of the tree is 4.

Write an algorithm to get the width of a binary tree.

Hint: a Breadth-First Search method may come to your mind immediately. However, can you use Depth First Search?

Solution: do a pre-order traversal. Using an array to keep track of the number of nodes in each level. When you visit a node, increment the number of the current level by 1. Since you won't visit it again, each tree node is counted only once.

Java语言: WidthOfBinaryTree

01 public int maxWidth(TreeNode root)
02 {
03     if(root==null)
04         return 0;
05     //define an array to record the number of nodes in each level
06     //assume the max number of levels is 1000
07     int []levels=new int[1000];
08     int max=0;
09     maxWidthHelper(levels,0,root);
10     //iterate through the level array, find max
11     for(int i=0;i<1000;i++)
12     {
13         if(levels[i]>max)
14         {
15             max=levels[i];
16         }
17     }
18     return max;
19 }
20 
21 public void maxWidthHelper(int [] levels, int depth, TreeNode root)
22 {
23     if(root==null)    return;
24     //visit this node, increment the number of nodes in the current level
25     levels[depth]++;
26     //DFS on children of the next level
27     maxWidthHelper(levels, depth+1, root.left);      
28     maxWidthHelper(levels, depth+1, root.right);      
29 }