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

## 4 comments

Your example is incorrect. A level traversal prints 1 2 3 4 5

Hi Rahan,

The example is correct. I am printing the left view of the tree. NOT the level order traversal.

Why to use an extra storage space – a queue?

called as viewLeft(root, -1, -1);

TimeComplexity : O(n)

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

Comments are closed.