CareerCup

it is simple. let the vertical no of root is 0. the vertical no of the one left to it is -1. and another one left to this is -2. similarly on the right side.

we can have a hash map in which we can insert the vertical nos. that is when we visit root we insert 0. when we visit one left we insert -1 if the hash does not contain -1 already. while inserting increase a counter.

finally counter is the no of verticals and hash is the vertical nos. from that we can say how many on the left or on the right

Here is a different solution,

puddleofriddles.blogspot.com/2012/01/count-total-number-of-vertical-columns.html

can u provide some more examples.

please clarify what do u mean by verticals? Is it all the paths from root to any leaf?

Sorry about the ambiguity. basically, from a given node, if you are traversing to left, your vertical position is shifted by -1 and if you are traversing right, your vertical position is shifted by +1.

i hope this clears the confusion.

Still not clear about what's the asking?

pls explain the question clearly...

I think it asks for (rightest's vertical - leftest's vertical + 1).

In order traversal. Have a counter. If node left is not null decrement counter. If node right is not null increment counter. Is this what the question meant?

typedef struct BNode
{
BTree *left;
BTree *right;
} BNode;
typedef BNode *BTree;

void doNumVert(BTree bt, int vert, int &leftest, int &rightest);
int numVert(BTree bt)
{
int leftest = 0;
int rightest = 0;

if (bt == NULL)
{
return 0;
}

doNumVert(bt, 0, leftest, rightest);

return rightest - leftest + 1;
}

void doNumVert(BTree bt, int vert, int &leftest, int &rightest)
{
if (bt->left)
{
doNumVert(bt->left, vert-1, leftest, rightest);
}
else
{
if (vert < leftest)
{
leftest = vert;
}
}

if (bt->right)
{
doNumVert(bt->right, vert+1, leftest, rightest);
}
else
{
if (vert > rightest)
{
rightest = vert;
}
}
}

Redefine BTree:
typedef struct BNode
{
BNode *left;
BNode *right;
} BNode, *BTree;