Home Trees Find the left view of a binary tree.

Find the left view of a binary tree.

by nikoo28

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)

	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);
		temp = Q -> front -> data;
		Q = deQueue(Q);
			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
				Q = enQueue(Q, NULL);
			// We are starting a new level, so we will toggle the flag.
			needToPrint = 1;
			// 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

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

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


You may also like


RaHan May 24, 2016 - 20:54

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

nikoo28 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.

Amit 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 ;
	if(*maxlevel info);
		*maxlevel = level;
	viewLeft(root->lchild, level, maxlevel);
	viewLeft(root->rchild, level, maxlevel);

called as viewLeft(root, -1, -1);
TimeComplexity : O(n)

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


Enclose codes in [code lang="JAVA"] [/code] tags

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