binary search tree width

[foxbrain]

hi
i need a code that compute the longest width of a binary tree in c++...
the idea is to go on each level of the tree and put it's width in an array then we see the highest number in that array.
so how can i program it ? can u write for me the code?
thanks

[BlackSheep]

No, we can't write your code for you. We can try to help you write it.
For a problem like this, couldn't you write a recursive function which checks both branches of the current node, and returns the length of the longer one?

[Gaminic]

I'm not sure I see the logic of using an array. What would myArray[0] be? The root? The leftmost leaf?

Anyway, I'm not entirely certain I know what you mean, but by width you mean the total number of leaves in a (sub)tree, right?
Thus, width(Node) = width(Node->left) + width(Node->right)?

This is a clear recurrence, and you could solve it by recursion:

int getWidth(Node* n) {
    if(n->isLeaf()) return 1;
    int width = 0;
    if (n->left != nullptr) width += getWidth(n->left);
    if (n->right != nullptr) width += getWidth(n->right);
    return width;
}

Note: no idea if this code is correct. Don't use it; it's just an example of how to build up the logic of a recurrence.

[foxbrain]

blacksheep: ok so help do it : what u said can be a solution to compute the hieght of a tree not the width
gaminic:no idon't want number of leaves, the width is :
example:
6
/ \
3 9
/ \ / \
1 5 4 15
/ /
0 21
so the width is 4

my idea is to go in breadth first traversal (6 then 3 then 9 then 1 then 5 then 4 then 15 then 0 then 21)
in each level i put the max number of node in an array then i compair the number in it......
here is the code of it's class:

# include<iostream>
using namespace std;
class node
{
public:
	int info;
	node* right;
	node* left;
	node()
	{
		info=0;
		right=left=0;
	}
	node(int data,node* left,node* right)
	{
		info=data;
		this->left=left;
		this->right=right;
	}
};
class bst
{
public:
	node* root;
	bst()
	{	root=0;}
	bst(node* root)
	{this->root=root;}
};

[Gaminic]

Again: you're not making your intentions clear. What do you plan to do with the array? What is the meaning of array[0], or array[l]? I can make an educated guess, but I don't feel like making assumptions on the basics of your question.

The only way to do a search in this way is by starting at the root and fetching a list of all nodes on the level below that. Then, the width of that level (which I imagine is your array index, but again, be more precise) is equal to the size of the list. The list will then be the input for the next iteration, where the process repeats itself.