Difficulty: Medium, Asked-in: Amazon, Qualcomm, Twitter, Flipkart, Ola, Paytm
Key takeaway: An excellent problem to learn problem-solving using pre-order and level order traversal of a binary tree.
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.
Examples
Input:
--> 1
/ \
--> 2 3
/ \ \
--> 4 5 6
Output: 1 2 4
Explanation: when we look from the left side,
nodes with values 1, 2 and 4 are visible.
Input:
--> 1
/ \
--> 2 3
\
--> 4
\
--> 5
Output: 1 2 4 5
Explanation: when we look from the left side,
nodes with values 1, 2, 4 and 5 are visible.
Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!
Solution idea and steps
If we observe closely, the nodes present in the left view will 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? Think!
While doing the level order traversal, whenever we complete the processing of the previous level, all the nodes of the current level will be present inside the queue. So now we can perform these operations to get the left view of the current level:
Solution pseudocode
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> LeftView
if (root == NULL)
return LeftView
Queue<TreeNode> Q
Q.enqueue(root)
while (Q.empty() == false)
{
int currLevelNodeCount = Q.size()
for (int i = 1; i <= currLevelNodeCount; i = i + 1)
{
TreeNode curr = Q.dequeue()
if (i == 1)
LeftView.push_back(curr->data)
if (curr->left != NULL)
Q.enqueue(curr->left)
if (curr->right != NULL)
Q.enqueue(curr->right)
}
}
return LeftView
}
Solution analysis
We are accessing each node only once using the level order traversal. So 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).
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 the preorder traversal and store the first node of that level in the output list.
The critical questions are: how do we track the level information during pre-order traversal? How do we find the first occurrence of each level? The idea is simple: 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
Solution pseudocode
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> LeftView
HashTable<int, int> H
storingLeftView(root, 1, H)
for (int i = 1; i <= H.size(); i = i + 1)
LeftView.push_back(H[i])
return LeftView
}
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.
Solution idea
The critical question is: Can we track the first occurrence of any level without using a hash table in the above code? Think!
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 level, and we insert its value in the output list or array. At the same time, we also update the max level visited so far with the current level.
Solution pseudocode
vector<int> leftViewBinaryTree(TreeNode root)
{
vector<int> LeftView
if (root == NULL)
return LeftView
int maxLevel = 0
storeLeftView(root, 1, &maxLevel, &LeftView)
return LeftView
}
void storeLeftView(TreeNode root, int level,
int* maxLevel, vector<int> &LeftView)
{
if (root == NULL)
return
if (*maxLevel < level)
{
LeftView.push_back(root->data)
*maxLevel = level
}
storeLeftView(root->left, level + 1, maxLevel, LeftView)
storeLeftView(root->right, level + 1, maxLevel, LeftView)
}
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 (LeftView.size() < level), it means we are at the new level. So 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 (LeftView.size() < level) becomes false, and we can skip all those nodes. If we again reach the next level, condition if (LeftView.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> LeftView
if (root == NULL)
return LeftView
storeLeftView(root, 1, &LeftView)
return LeftView
}
void storeLeftView(TreeNode root, int level, vector<int> &LeftView)
{
if (root == NULL)
return
if (LeftView.size() < level)
LeftView.push_back(root->data)
storeLeftView(root->left, level + 1, LeftView)
storeLeftView(root->right, level + 1, LeftView)
}
Solution analysis
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!
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!