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.

Input: Sample Tree (Pointer to node 1 is given).
Output: 1, 2, 4

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. :)