enjoyalgorithms

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

  • Iterative approach using level order traversal
  • Recursive approach using preorder traversal and hashing
  • Efficient approach using recursive pre-order traversal

Iterative approach using level order traversal

Solution idea

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 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? Let's 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, the front node of the queue will be the first node, which will be the left view of the current level.

Solution steps

Step 1: We define an output list leftView to store the left view of the tree.

Step 2: Now, we create a queue and initialize it with the root node to traverse the tree using level order traversal.

Step 3: We run a loop till the queue is not empty.

  • We first store the count of nodes at the current level in a variable currLevelNodeCount. This will be equal to the size of the queue.
  • Now, we run an inner loop from i = 1 to currLevelNodeCount. We dequeue the front node and start adding next-level nodes to the queue.
  • During this procedure, if i == 1, we add the first node of the current level to the output list leftView.
  • After this inner loop, the processing of nodes at the current level is done. Now, we can move to the next level and continue a similar process.

Step 4: After the end of the outer loop, we return the leftView as an output.

Implementation code C++

vector<int> leftViewBinaryTree(TreeNode* root) 
{
    vector<int> leftView;
    if (root == NULL)
        return leftView;

    queue<TreeNode*> Q;
    Q.push(root);

    while (!Q.empty()) 
    {
        int currLevelNodeCount = Q.size();

        for (int i = 1; i <= currLevelNodeCount; i = i + 1) 
        {
            TreeNode* curr = Q.front();
            Q.pop();
            if (i == 1)
                leftView.push_back(curr->data);

            if (curr->left != NULL)
                Q.push(curr->left);

            if (curr->right != NULL)
                Q.push(curr->right);
        }
    }

    return leftView;
}

Implementation code Python

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def leftViewBinaryTree(root):
    leftView = []
    if root is None:
        return leftView

    queue = deque()
    queue.append(root)

    while queue:
        currLevelNodeCount = len(queue)

        for i in range(1, currLevelNodeCount + 1):
            curr = queue.popleft()

            if i == 1:
                leftView.append(curr.data)

            if curr.left:
                queue.append(curr.left)

            if curr.right:
                queue.append(curr.right)

    return leftView

Implementation code Java

public class LeftViewBinaryTree 
{
    public static List<Integer> leftViewBinaryTree(TreeNode root) 
    {
        List<Integer> leftView = new ArrayList<>();
        if (root == null)
            return leftView;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (queue.isEmpty() == false) 
        {
            int currLevelNodeCount = queue.size();

            for (int i = 1; i <= currLevelNodeCount; i = i + 1) 
            {
                TreeNode curr = queue.poll();

                if (i == 1)
                    leftView.add(curr.data);

                if (curr.left != null)
                    queue.offer(curr.left);

                if (curr.right != null)
                    queue.offer(curr.right);
            }
        }

        return leftView;
    }
}

Time and space complexity analysis

We access each node only once using the level order traversal. So, time complexity = O(n). We use a queue, which will take O(w) space, where w is the width of the tree. So, space complexity = O(w).

  • For a skewed tree, space complexity = O(1).
  • For a balanced tree, the space complexity = O(n).

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!

In preorder traversal, we first visit the root node, then visit all the nodes in the left subtree, and finally visit 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 preorder 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 arguments 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

Step 1: We define a function leftViewBinaryTree(root) that returns the left view of the tree.

Step 2: To store the output, we declare a list called leftView.

Step 3: We also declare a hash table H to store the first node of each level.

Step 4: 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. Whenever we visit a level:

  • We search the current level in 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.

Step 5: When all the nodes are visited using the preorder traversal, the hash table will store the left view of the tree. Inside the leftViewBinaryTree(root) function, we traverse the hash table and store all the values in the leftView list to obtain the left view.

Step 6: Finally, we return the leftView list.

Implementation code C++

void storingLeftView(TreeNode* root, int level, unordered_map<int, int>& H) 
{
    if (root == NULL)
        return;
    
    if (H.find(level) == H.end())
        H[level] = root->data;
    
    storingLeftView(root->left, level + 1, H);
    storingLeftView(root->right, level + 1, H);
}

vector<int> leftViewBinaryTree(TreeNode* root) 
{
    vector<int> LeftView;
    unordered_map<int, int> H;
    storingLeftView(root, 1, H);

    for (int i = 1; i <= H.size(); i = i + 1)
        LeftView.push_back(H[i]);

    return LeftView;
}

Implementation code Python

def storingLeftView(root, level, H):
    if root is None:
        return

    if level not in H:
        H[level] = root.data

    storingLeftView(root.left, level + 1, H)
    storingLeftView(root.right, level + 1, H)

def leftViewBinaryTree(root):
    LeftView = []
    H = {}
    storingLeftView(root, 1, H)

    for i in range(1, len(H) + 1):
        LeftView.append(H[i])

    return LeftView

Implementation code Java

class LeftViewBinaryTree 
{
    private Map<Integer, Integer> H;

    private void storingLeftView(TreeNode root, int level) 
    {
        if (root == null)
            return;

        if (H.containsKey(level) == false)
            H.put(level, root.data);

        storingLeftView(root.left, level + 1);
        storingLeftView(root.right, level + 1);
    }

    public List<Integer> leftViewBinaryTree(TreeNode root) 
    {
        List<Integer> LeftView = new ArrayList<>();
        H = new HashMap<>();
        storingLeftView(root, 1);

        for (int i = 1; i <= H.size(); i = i + 1)
            LeftView.add(H.get(i));

        return LeftView;
    }
}

Time and space complexity 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 recursive 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).

Efficient 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? Let's think!

The idea is to traverse the tree in a preorder manner and, at the same time, maintain a variable to track the maximum level visited so far. If the current level is greater than the maximum level visited so far, then the current node is the first node of that level, and we insert its value into the output list. During this process, we also update the maximum level visited so far with the current level.

Implementation code C++

class LeftViewBinaryTree 
{
private:
    int maxLevel;
    vector<int> LeftView;

    void storeLeftView(TreeNode* root, int level) 
    {
        if (root == NULL)
            return;
        if (maxLevel < level) 
        {
            LeftView.push_back(root->val);
            maxLevel = level;
        }
        
        storeLeftView(root->left, level + 1);
        storeLeftView(root->right, level + 1);
    }

public:
    vector<int> leftViewBinaryTree(TreeNode* root) 
    {
        maxLevel = 0;
        LeftView.clear();
        storeLeftView(root, 1);
        return LeftView;
    }
};

Implementation code Python

class LeftViewBinaryTree:
    def __init__(self):
        self.maxLevel = 0
        self.leftView = []

    def storeLeftView(self, root, level):
        if root is None:
            return

        if self.maxLevel < level:
            self.leftView.append(root.val)
            self.maxLevel = level

        self.storeLeftView(root.left, level + 1)
        self.storeLeftView(root.right, level + 1)

    def leftViewBinaryTree(self, root):
        self.maxLevel = 0
        self.leftView = []
        self.storeLeftView(root, 1)
        return self.leftView

Implementation code Java

class LeftViewBinaryTree 
{
    private int maxLevel;
    private List<Integer> leftView;

    private void storeLeftView(TreeNode root, int level) 
    {
        if (root == null)
            return;

        if (maxLevel < level) 
        {
            leftView.add(root.val);
            maxLevel = level;
        }

        storeLeftView(root.left, level + 1);
        storeLeftView(root.right, level + 1);
    }

    public List<Integer> leftViewBinaryTree(TreeNode root) 
    {
        maxLevel = 0;
        leftView = new ArrayList<>();
        storeLeftView(root, 1);
        return leftView;
    }
}

Another implementation using preorder traversal

Instead of using a variable to track the maximum level visited so far, we can check the size of the output list during the preorder traversal. If the size of the output list is less than the current level, it indicates that we are at a new level. In this case, we insert the current node into the output list as the left view of that level.

  • Now at this point, the size of the output list is equal to the current level. If we explore any other nodes at the same level, the condition if (size of the output list < level) becomes false, allowing us to skip those nodes.
  • When we reach the next level, the condition if (size of the output list < level) becomes true again, and we add the current node to the output list. So, this idea will help us to track the first node at each level.

Implementation code C++

class BinaryTreeLeftView 
{
private:
    vector<int> leftView;

    void storeLeftView(TreeNode* root, int level) 
    {
        if (root == NULL)
            return;

        if (leftView.size() < level)
            leftView.push_back(root->data);

        storeLeftView(root->left, level + 1);
        storeLeftView(root->right, level + 1);
    }
    
public:
    vector<int> leftViewBinaryTree(TreeNode* root) 
    {
        leftView.clear();
        if (root == NULL)
            return leftView;
        
        storeLeftView(root, 1);
        return leftView;
    }
};

Implementation code Python

class BinaryTreeLeftView:
    def __init__(self):
        self.leftView = []

    def storeLeftView(self, root, level):
        if root is None:
            return

        if len(self.leftView) < level:
            self.leftView.append(root.data)

        self.storeLeftView(root.left, level + 1)
        self.storeLeftView(root.right, level + 1)

    def leftViewBinaryTree(self, root):
        self.leftView.clear()
        if root is None:
            return self.leftView
        
        self.storeLeftView(root, 1)
        return self.leftView

Implementation code Java

class BinaryTreeLeftView 
{
    private List<Integer> leftView;

    private void storeLeftView(TreeNode root, int level) 
    {
        if (root == null)
            return;

        if (leftView.size() < level)
            leftView.add(root.data);

        storeLeftView(root.left, level + 1);
        storeLeftView(root.right, level + 1);
    }

    public List<Integer> leftViewBinaryTree(TreeNode root) 
    {
        leftView = new ArrayList<>();
        if (root == null)
            return leftView;

        storeLeftView(root, 1);
        return leftView;
    }
}

Time and space complexity analysis

We are visiting each node using pre-order traversal and performing O(1) operation with each node. So, time complexity = O(n).

Space complexity = The size of the call stack used by recursion = O(h), where h is the height tree. The size of the call stack will be O(n) for a skewed tree and O(log n) for a balanced tree.

Critical ideas to think!

  • Why do we use a queue in level order traversal?
  • Can we solve this problem using iterative preorder traversal using a stack?
  • Can we think of solving 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.
  • Can we implement the 3rd approach by using maxLevel as a pointer parameter in the function call?
  • In the final solution, why are we doing the comparison if (leftView.size() < level)?
  • In the 1st solution, 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!

More from EnjoyAlgorithms

Self-paced Courses and Blogs