Find width of a tree pointed by head


Considering that the width of the tree is defined as the maximum number of nodes at any one level, the following code should hold good. Drop a comment if you think that this code s***s [:)]

public void maxWidthBST(NodeType rootNode)
        {
            int level=depthBST(rootNode);           
            int maxWidth=0;
            int intNodeCount=0;
            for(int counter=1; counter<=level;counter++)
            {
                intNodeCount = NodeCount(rootNode, counter);
                if(intNodeCount>maxWidth)
                {
                    maxWidth = intNodeCount;
                }   
            }
            Console.WriteLine(“The maximum width is: ” + maxWidth);
        }       

        public int NodeCount(NodeType root, int level)
        {
            int LWidth=0;
            int RWidth=0;
            int totalNodesAtLevel=0;
            if(level<=0) return 0;
            if(level==1)return 1;
            if(level>1)
            {
                if(root.Left !=null) LWidth=NodeCount(root.Left, level-1);
                if(root.Right !=null) RWidth= NodeCount(root.Right, level-1);
                totalNodesAtLevel = LWidth+RWidth;           
            }
            return totalNodesAtLevel;
        }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s