In this post, we will discuss a method to print the left view of a binary tree. This is one the most common easy level interview questions. Also, you might get to see interview questions which can be solved with slight variations to this code.
First, let's see what do we mean by the left view of a binary tree. The left view contains all nodes that are first nodes in their levels. Left View of a tree is defined as the nodes that would be visible to us from the left side. To do this we have to simply print the first node encountered while traversing a level from the left. Have a look at the below image to get some idea.
There are 2 solutions to this problem, first is to do a recursive preorder traversal in which we maintain max level we have traversed and then print the node if the max level is less than the max_level variable and update the max_level variable, another simple solution is to do level order traversal and print the first node in every level.
Method 1: Using Recursive Preorder traversal
Most of the problems related to trees can be solved with little modifications to the basic preorder traversal code. For this method, we do the following steps.
Let's have a look at the code
Method 2: Using BFS traversal (using queue)
This is an iterative approach in which we use a queue to store the nodes in the next level and then print the leftmost node in each level.
Let's have a look at the code.
You might also be interested in
Right View of a Binary Tree
First, let's see what do we mean by the left view of a binary tree. The left view contains all nodes that are first nodes in their levels. Left View of a tree is defined as the nodes that would be visible to us from the left side. To do this we have to simply print the first node encountered while traversing a level from the left. Have a look at the below image to get some idea.
Left view of a binary tree |
There are 2 solutions to this problem, first is to do a recursive preorder traversal in which we maintain max level we have traversed and then print the node if the max level is less than the max_level variable and update the max_level variable, another simple solution is to do level order traversal and print the first node in every level.
Method 1: Using Recursive Preorder traversal
Most of the problems related to trees can be solved with little modifications to the basic preorder traversal code. For this method, we do the following steps.
- We create a variable max_level that denotes the max level traversed and we create a variable level that denotes the current level being traversed.
- We check if the level of the current node is greater than the max_level. if yes then we print the current node and update the max_level else we move ahead.
- In each recursive call, we increase the current level by one as we travel down the binary tree.
Let's have a look at the code
C++ Program
Sample input and output to check the program
Method 2: Using BFS traversal (using queue)
This is an iterative approach in which we use a queue to store the nodes in the next level and then print the leftmost node in each level.
- Create an empty queue and put the head node into it.
- Create a max_level variable to denote the current level being traversed, and a variable current_node to denote the current node being processed.
- If the level of the current_node is greater than the max_level then do the following steps:
- print the value of the current_node.
- set max_level to the level of the current node.
- Enqueue the left child of the current node and then the right child of the current_node in the queue.
- Do the steps 2 to 4 till queue is empty.
Let's have a look at the code.
C++ Program
Sample input and output to check the program
You might also be interested in
Right View of a Binary Tree
Comments
Post a Comment