Monday, May 4, 2015

Right view of binary tree

Problem: Right view of a binary tree is set of nodes visible when tree is visited from right side. Write a program to print the right view of a binary tree.

Approach: Do level order traversal and print the last node in every level.

Implementation:

//Public interface
void BSTree::rightView()
{
if(root)
rightView(root);
}

//Actual implementation
void BSTree::rightView(Node* node)
{
std::queue<Node*> q[2];
bool turn = 0;
q[turn].push(node);
while(!q[0].empty() || !q[1].empty())
{
if(!q[turn].empty())
{
int dataToPrint = 0;
while(!q[turn].empty())
{
Node* temp = q[turn].front();
if(temp->left)
q[!turn].push(temp->left);
if(temp->right)
q[!turn].push(temp->right);
q[turn].pop();
dataToPrint = temp->data;
}
std::cout<<dataToPrint<<'\t';
turn = !turn;
}
}
}

Complexity: O(n)

No comments:

Post a Comment