2.1K
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:-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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?
voidviewLeft(structtreenode *root,intlevel,int*maxlevel){if(root == NULL)return;level++;if(*maxlevel info);*maxlevel = level;}viewLeft(root->lchild, level, maxlevel);viewLeft(root->rchild, level, maxlevel);}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.