Amazon Question: Find number of vertical lines that can cover whole nodes of Binary Tree

Solution:

1. Do a preorder traversal.
2. Initialize count to 0.
3. Whenever encounter a left node increase count by 1.
4. Whenever encounter a right node decrease count by 1.
5. Return maxCount - minCount + 1.

Source Code:

int BTree::findVerticalLinesToCut(Node* node, int count)
{
static int max = 0, min = 0;
if(node)
{
max = max < count? count : max;
min = min > count ? count : min;

if(node->left)
{
findVerticalLinesToCut(node->left, count+1);
}
if(node->right)
{
findVerticalLinesToCut(node->right, count-1);
}
}
return max - min + 1;
}