**Difficulty:** Medium, **Asked-in:** Amazon, Qualcomm, Twitter, Flipkart, Ola, Paytm

### Let’s understand the problem

Write a program to find the left view of the given binary tree. The left view of a binary tree is a group of nodes visible when viewed from the left side or when the tree is visited from the left side.

**Important note:** before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

**Examples**

```
Input:
1
/ \
2 3
/ \ \
4 5 6
Output: 1 2 4
Input:
1
/ \
2 3
\
4
\
5
Output: 1 2 4 5
```

### Discussed solution approaches

- An iterative approach using level order traversal
- A recursive approach using preorder traversal and hashing
- An effcient approach using recursive pre-order traversal

### Solution approach 1 : An iterative approach using level order traversal

**Solution idea and steps**

If we observe closely, the nodes present in the left view would be the first node of each level. So one idea would be to traverse the tree using the level order traversal, access the first node of each level, and add it to the output list. The critical question is: how can we get the first node present at each level?

The idea is: while doing the level order traversal, whenever we move down to a new level:

- We add the first node of the new level to the output list.
- We count the number of nodes at the current level.
- Using a loop, we start adding next-level nodes to the queue till the count of nodes at the current level is 0.
- After this, we move to the next level and continue a similar process.

**Solution pseudocode C++**

```
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> result
if (root == NULL)
return result
Queue<TreeNode> Q
Q.enqueue(root)
while (Q.empty() == true)
{
int n = Q.size()
for (int i = 1; i <= n; i = i + 1)
{
TreeNode curr = Q.dequeue()
if (i == 1)
result.push_back(curr->data)
if (curr->left != NULL)
Q.enqueue(curr->left)
if (curr->right != NULL)
Q.enqueue(curr->right)
}
}
return result
}
```

**Solution analysis**

It works in linear time complexity as the algorithm explores each node once. Or in other words, the time complexity is equal to the time complexity of the level order traversal. Time complexity = O(n)

Similarly, we use a queue that will take O(w) space, where w is the width of the tree. Space complexity = O(w).

- For a skewed tree, space complexity = O(1)
- For a balanced tree, space complexity = O(n)

### Solution approach 2 : A recursive approach using preorder traversal and hashing

**Solution idea**

The critical question is: can we solve this problem using recursive tree traversal? Let's think!

Preorder traversal first visits the root node, then visits all the nodes in the left subtree, and finally visits all the nodes in the right subtree. So another idea would be to identify the first occurrence of each level during preorder traversal and store the value of the first node in the output list. We can track the level of the tree in the function argument and use a hash table to check the first occurrence of each level. We store each level as a key and its first node as a value in the hash table.

**Solution steps**

- We define a function
**leftViewBinaryTree(root)** which returns the left view of the tree in an ArrayList or vector.
- Inside the function, we declare an ArrayList or vector
**result** to store the output.
- We also declare a hash table
**H** to store the first node of each level.
- Now we use a helper function
**storingLeftView(root, level, H)** to traverse the tree in a preorder fashion and store the leftmost node of each level in the hash table H. Initially hash table is empty and the level value is 1. Whenever we visit a level during the preorder traversal:
- We search the current level into the hash table. If the level information is not there, it means, the current level is visited for the first time. So we insert the current node's value with the current level as a key into the hash table H.
- Otherwise, we ignore the current node and move to the next node in the preorder traversal.
- When all the nodes are visited using the preorder traversal, the hash table will store the left view of the tree. So inside the function
**leftViewBinaryTree(root),** we traverse the hash table and store all the values in the output array or list to get the left view.
- We finally return the output list result.

**Solution pseudocode C++**

```
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> result
HashTable<int, int> H
storingLeftView(root, 1, H)
for (int i = 1; i <= H.size(); i = i + 1)
result.push_back(H[i])
return result
}
void storingLeftView(TreeNode root, int level, HashTable<int, int> &H)
{
if (root == NULL)
return
if (H.search(level) == false)
H[level] = root->data
storingLeftView(root->left, level + 1, H)
storingLeftView(root->right, level + 1, H)
}
```

**Solution analysis**

Time complexity = Time complexity of the pre-order traversal + Time complexity to transfer left view from the hash table to the output list = O(n) + O(n).

Space complexity = Space complexity of the pre-order traversal + Space complexity of storing left view in the hash table = O(h) + O(h) = O(h), where h is the height tree. The space used by the hash table and the call stack is equal to the height of the tree.

- For a skewed tree, space complexity = O(n)
- For a balanced tree, space complexity = O(log n)

### Solution approach 3 : An effcient approach using recursive pre-order traversal

**Solution idea**

The critical question is: Can we track the first occurrence of any level without using a hash table in the above code?

The idea is to traverse the tree in the preorder manner and, at the same time, maintain a pointer variable in the function parameter to track the max level visited so far. If the current level is more than the max level visited so far, then the current node is the first node of that particular level, and we insert its value in the output list or array. At the same time, we update the max level visited so far with the current level.

**Solution pseudocode C++**

```
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> result
if (root == NULL)
return result
int maxLevel = 0
storeLeftView(root, 1, &maxLevel, &result)
return result
}
void storeLeftView(TreeNode root, int level,
int* maxLevel, vector<int> &result)
{
if (root == NULL)
return
if (*maxLevel < level)
{
result.push_back(root->data)
*maxLevel = level
}
storeLeftView(root->left, level + 1, maxLevel, result)
storeLeftView(root->right, level + 1, maxLevel, result)
}
```

#### Another smart implementation using preorder traversal

Instead of passing a pointer to track the max level visited so far, we can check the size of the output list during the preorder traversal. If the output list size is less than the value of the current level i.e. **if (result.size() < level)**, it means we are at the new level, and we insert the current node into the output list as the left view of that level.

- Now output list size is equal to the current level. If we access any other nodes at the same level, the condition if (result.size() < level) becomes false, and we can skip all those nodes.
- If we again reach the next level, condition if (result.size() < level) becomes true, and we add the current node into the output list. In such a way, we can keep track of the first node at each level.

```
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> result
if (root == NULL)
return result
storeLeftView(root, 1, &result)
return result
}
void storeLeftView(TreeNode root, int level, vector<int> &result)
{
if (root == NULL)
return
if (result.size() < level)
result.push_back(root->data)
storeLeftView(root->left, level + 1, result)
storeLeftView(root->right, level + 1, result)
}
```

**Solution analysis**

- We are visiting each node using pre-order traversal and performing O(1) operation with each node. Time complexity = O(n).
- Space Complexity = O(h), where h is the height tree. For a skewed tree, it uses O(n) space for the call stack. For a balanced tree, the call stack uses O(log n) space.

**Important note:** we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

### Critical ideas to think!

- Why do we use a queue in a level order traversal?
- Can we solve this problem using iterative preorder traversal using stack?
- Can we think to solve this problem using in-order or post-order traversal?
- Can we modify the above solutions to print the right view of the tree?
- Explore the worst and best space complexities in the above approaches?
- In the 3rd approach, what is the reason to send maxLevel as a pointer instead of an integer? Can we solve it using maxLevel as a static or global variable?
- In the final solution, why are we doing the comparison if (result.size() < level)?
- In the first solution using the queue, can we use a level separator to identify a new level in the tree?

### Similar coding problems to practice

Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!