Home Trees Find the left view of a binary tree.

Find the left view of a binary tree.

by nikoo28
4 comments

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

You may also like

4 comments

RaHan May 24, 2016 - 20:54

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

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

Reply
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 ;
	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)

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

Reply

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