Monday, May 4, 2015

Left view of binary tree

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

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

Implementation: 

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

//Actual implementation
void BSTree::leftView(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())
{
std::cout<<q[turn].front()->data<<'\t';
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();
}
turn = !turn;
}
}
}

Complexity: O(n)

No comments:

Post a Comment