CareerCup

bfs
level-wise traverse

void get_min_max_offset( const Node * root, int offset, int & min, int & max )
{
   if( root == 0 )
   {
      return;
   }

   if( min > offset )
   {
      min = offset;
   }

   if( max < offset )
   {
      max = offset;
   }

   get_min_max_offset( root->left, offset - 1, min, max );
   get_min_max_offset( root->right, offset + 1, min, max );
}

int get_tree_width( const Node * root )
{
   if( root == 0 )
   {
      return 0;
   }

   int min = INT_MAX;
   int max = INT_MIN;

   get_min_max_offset( root, 0, min, max );

   return 1 + max - min;
}

A tree is not necessarily a binary tree. It could be any type of tree. The width of a tree is supposed to be the maximal number of nodes in one level of the tree.

int left, right;

int f(NODE* r, int i)
{
  if(i>right)
  {
    right=i;
  }

  if(i<left)
  {
    left=i;
  }
  
  if(r->l)
  {
    f(r->l, i-1);   
  }   

  if(r->r)
  {
    f(r->r, i+1);
  }
}

void main()
{
  left=right=0;    
  f(r, 0);
  width=right-left+1;
}

what would be the initial value for i

findWidth(Node root){
 if(numChild(root) <= 1) /*numChild(root) returns # of children*/
  return 1;
 
 width = 0;
 for each child of root{
  width += findWidth(child);
 }

 return width;
}

In above function I have assumed that width does not have to be max number of nodes on same level.
Can somebody clarify whether width is max number of nodes on same level or levels can be at different levels? [If nodes have to be on same level then BFS should work]

Can we proceed with finding the height of a tree.

PLZ let me know.

No, width hasn`t been found yet and nobody can tell the exact definition of a width of a tree, neither do I, but I`d like to get to know.

The width of the trees number of columns you can find in the tree... for example:
A
B C
D E F
has width = 5 where first column has D second has B third has A and E, forth has C and fifth has F
Hope someone can solve this question

vinaysachdeva23, please, can you give the source (book or prooflink or article) of definition of width you gave? I couldn`t find

// Assuming the definition of tree width is the max number of nodes in any level of the tree:

// Perform Level Order Traversal, with additional variable called level_number being pushed into the queue

int findWidth(struct node *head) {
    int prevlevel=-1;
    int currlevel=-1;
    int maxwidth=0;
    int width=0;
    q.queue(head);
    q.queue(1);
    while(!q.empty()) {
        struct node n=q.dequeue();
        currlevel=q.dequeue();
        if(currlevel!=prevlevel) {
           if(width>maxwidth)
                maxwidth=width;
           width=0;
        }
        width++;
        // Queue all children and their levels
        if(n.left!=NULL) {
            q.queue(n.left);
            q.queue(currlevel+1);
        }
        if(n.right!=NULL) {
            q.queue(n.right);
            q.queue(currlevel+1);
        }
        prevlevel=currlevel;
    }
    if(width>maxwidth)
          maxwidth=width;
    return maxwidth;
}

the definition is sort of flawed. imagine a tree with 10 levels. root has left and right child. but left child ahs only left child, which has only left child, and so on for remaining 8 levels. same for right child (only right childs) at lowermost level tree has 2 nodes, but as far apart as possible. arguably this tree is wide than a 2 level tree with a root having left and right child, both being leaf nodes. either tree has 2 nodes in leaf level.

i think the point of the question is to see how candidate can try to zero in on a definition of a vague concept like tree width. ideally they would want to see elimination of simple and inaccurate definitions while working through scenarios. Otherwise just counting leaf nodes is trivial.

The question is about the width of a tree not the maximum number of nodes on a particular level...
The width of a tree means how wide it is.
Like as explained above by xenon, the width of tree is not equal to 2 but will be much more than 2 as it extends too wide in 10 levels.
So its clear that the width means the extension of tree not the max number of nodes on a particular level.
If that would have been the case, then a tree with 3 levels would have had same width as a tree with 10 levels(above tree) which contradictorily proves wrong.
Hence the width of a tree actually means how wide it is.

Still dont get it(( For example, tree described above with only left childs in the left subtree and right childs in the right one and depth = 8 would be very wide and its width won`t be be 2^8 = 256? What is the formala to calculate width for each tree?

For example, the height is the longest path from root to leaves, but what about width? How it`s gonna be found?

ок, your examples made it all clear to me, now i get it) appreciate your help, thanks)

http: en.wikipedia.org wiki Tree_decomposition

A
B C
D
E F
G H I J

i think the max width is '4' b/w g and c

public Integer width()
{
	LinkedList<Node1> queue = new LinkedList<Node1>();//for level operations
	ArrayList<Integer> level = new ArrayList<Integer>();//list of counts at each level
	int levelCount = 0;//count at each level
	if(root!=null)
	{
		queue.add(root);
		levelCount = 1;
	}
	while(queue.size()>0)//to check if we reach leaf nodes
	{
		level.add(levelCount);
		while(levelCount>0)
		{
			Node1 node = queue.removeFirst();
			if(node.left!=null)queue.add(node.left);
			if(node.right!=null)queue.add(node.right);
			--levelCount;
		}
		levelCount = queue.size();//at this level we get the total nodes at one level
	}
	
	//naive approach for finding Max. Can be replaced by a priority queue 
	Iterator<Integer> levelItr = level.iterator();
	int Max = 0;
	while(levelItr.hasNext())
	{int temp = levelItr.next().intValue();
	Max = Max>temp?Max:temp;
	}
	
return Max;	
}

i think width can be found out by MAX(going left of each node until leftchild is NULL + same for right + 1) which can be solved recursively as:

int width(node *sr,node *k)
{
if(k == NULL)
return 0;
static int max;
int l = width(k,k->leftchild);
int r = width(k,k->rightchild);
if(l+r+1 > max)
max = l+r+1;
if(sr == NULL)
return max;
else if(k == sr -> leftchild)
return l+1;
else
return r+1;
}

sry it wont work for some cases pls go forward using my code.....

width(node* N)
{
int count++;
count=leftwidth(N->left,count);
count=rightwidth(N->right,count);
print(count);
}

leftwidth(Node N,count)
{
if(n!=null)
{
count++;
n=n->left;
}
return count;
}
rightwidth(Node N,count)
{
if(n!=null)
{
count++;
n=n->right;
}
}

let me know if anything is wrong..

Considering that the width is maximum number of nodes at any one level, the code below should work. No??

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

www cs duke edu/courses/spring00/cps100/assign/trees/diameter html
replace " " by "."

Check this implementation in C, without using level order traversal techcrashcourse.com/2016/06/program-to-find-maximum-width-of-binary-tree.html