1.

Write a function to connect nodes at the same level of a binary tree

Answer»

Input:              100    

                        /     \                

                   13      15   

                   /  \         \       

              14    1        20 

     

Output:          100-> NULL    

                        /      \                

                  13   ->  15   -> NULL

                  /      \           \       

               14  ->  1   -> 20 -> NULL

class Solution
{
public:
//Function to connect nodes at the same level.
void connect(Node *p)
{
map<int,vector<Node *> > m;
queue<Node *> q;
queue<int> l;
q.push(p);
l.push(0);
while(!q.empty())
{
Node *temp=q.front();
int level=l.front();
q.pop();
l.pop();
m[level].push_back(temp);
if(temp->left!=NULL)
{
q.push(temp->left);
l.push(level+1);
}
if(temp->right!=NULL)
{
q.push(temp->right);
l.push(level+1);
}
}
for(map<int,vector<Node *> > ::iterator it=m.begin();it!=m.end();it++)
{
vector<Node *> temp1=it->second;
for(int i=0;i<temp1.size()-1;i++)
{
temp1[i]->nextRight=temp1[i+1];
}
temp1[temp1.size()-1]->nextRight=NULL;
}
}
};


  • Time Complexity: O(n)


  • Space Complexity: O(n)


Discussion

No Comment Found

Related InterviewSolutions