Print Left View of a Binary Tree

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.

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.

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!

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 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:

• We first count the number of nodes at the current level, which will be equal to the size of the queue. currLevelNodeCount = Q.size().
• Now using a loop from i = 1 to currLevelNodeCount, we start adding next-level nodes to the queue. During this procedure, we add the first node of the current level to the output list i.e. if(i == 1), LeftView.push_back(curr->data). Note: We are using an Arraylist or vector LeftView to store the output.
• After this loop, the processing of nodes at the current level is done. Now we can move to the next level and continue a similar process.

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

• 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 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

• We define a function leftViewBinaryTree(root) which returns the left view of the tree in an ArrayList or vector.
• To store the output, we declare an ArrayList or vector LeftView inside the function. 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.
• 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 list to get the left view.
• We finally return the output list LeftView.

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.

• 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? 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)
}

Another 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 (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

• 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 (LeftView.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

• Print the right view of the binary tree
• Print the top view of the binary tree
• Print the bottom view of the binary tree
• Boundary Traversal of binary tree
• Vertical Order Traversal of a Binary Tree

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!