Interview Question
Country: United States
int DepthIterative(class tree* root)
{
queue<class tree*> q;
int depth = 0;
int evenC = 0, oddC = 0;
bool even = false, odd = false;
if(!root)
return 0;
q.push(root);
oddC++;
odd = true;
while(!q.empty())
{
if(odd)
{
for(int i=0;i<oddC;i++)
{
class tree* temp = q.front();
q.pop();
if(temp->left)
{
evenC++;
even = true;
q.push(temp->left);
}
if(temp->right)
{
evenC++;
even = true;
q.push(temp->right);
}
}
odd = false;
oddC = 0;
depth++;
}
if(even)
{
for(int i=0;i<evenC;i++)
{
class tree* temp = q.front();
q.pop();
if(temp->left)
{
oddC++;
odd = true;
q.push(temp->left);
}
if(temp->right)
{
oddC++;
odd = true;
q.push(temp->right);
}
}
even = false;
evenC = 0;
depth++;
}
}
return depth;
}
Implement a DFS using a stack or a BFS using a queue.
- inucoder April 30, 2015