Home Trees Find the left view of a binary tree.

# Find the left view of a binary tree.

Question: Given the root pointer to a binary tree, find the left view of the tree.

At a single glance of the problem, we can understand that we need to perform a level order traversal on the tree. This is similar to finding the number of levels in a tree. At the start of each level, we just print the first element.
This can be done with the algorithm below:-

void leftViewOfBinaryTree(struct binaryTreeNode * root)
{
// Level order traversal
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;

// Maintain a level count
int level = 0;

if(root == NULL)
return;

Q = enQueue(Q, root);

//print the root
printf("%d ",root->data);

// a flag to check if we need to print
int needToPrint = 0;

// Now the first level will end over here,
// So append a NULL node
Q = enQueue(Q, NULL);

while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);

if(needToPrint)
{
printf("%d ", temp->data);

// toggle the flag
needToPrint = 0;
}

// If we encounter a NULL, that means an end of a level
// And we need to increment the level count
if(temp == NULL)
{
// Put the marker for next level also
if(!isQueueEmpty(Q))
Q = enQueue(Q, NULL);

level++;

// We are starting a new level, so we will toggle the flag.
needToPrint = 1;
}
else
{
// We continue with the level order traversal
if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
}
// Delete the queue
free(Q);
}


Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for the running code:- http://ideone.com/PaJPER

#### You may also like May 24, 2016 - 20:54

Your example is incorrect. A level traversal prints 1 2 3 4 5 May 27, 2016 - 10:40

Hi Rahan,

The example is correct. I am printing the left view of the tree. NOT the level order traversal. March 14, 2015 - 18:58

Why to use an extra storage space – a queue?

void viewLeft(struct treenode *root, int level, int *maxlevel)
{
if(root == NULL)
return ;
level++;
if(*maxlevel info);
*maxlevel = level;
}
viewLeft(root-&gt;lchild, level, maxlevel);
viewLeft(root-&gt;rchild, level, maxlevel);
}


called as viewLeft(root, -1, -1);
TimeComplexity : O(n) March 16, 2015 - 00:53

Hi Amit,

Thanks for the new approach. The approach discussed in the above post is an iterative one, while you are following a recursive approach. A recursive call back will also maintain a stack of n calls in the worst case. :)

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More