Print left view of a binary tree

Given a binary tree, print the values of nodes which would be present in left view of binary tree. A node will be in the left-view if it is the left-most node at its level (imagine level order traversal). For example,    

                1
          2             3
      4      5       6  
        8              9
          10

In the above tree,
node 1 is left-most node for level 0.
node 2 is left-most node for level 1.
node 4 is left-most node for level 2.
node 8 is left-most node for level 3.
node 10 is left-most node for level 4.
              
And therefore left view for this tree is 1,2,4,8,10


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

If we do a level order traversal of tree such that the left most node of each level is visited before all other nodes in that level then all we need to do is to print out the first visited node at each level to print the left view of tree. This can be done by doing a level order traversal from left end to right end and keeping track of max-level seen so far to find out when the new level starts. As soon as we find out that the new level has started, we print out the current node that is being visited.

The steps for this algorithm are -
1. Initialize maxLevelSeenSoFar to -1 and call printLeftViewLevelOrder(currentNode = root)
2. In function printLeftViewLevelOrder if currentNode is null, do nothing and return.
3. Else, add tuple (node = currentNode, level = 0) to the 'queue'.
4. while 'queue' is not empty do
       - remove the first tuple(currentNode, level) from the queue.
       - if (level > maxLevelSeenSoFar) then we know that we are starting to traverse a new level and this is the first(and left most) node for this new  level and therefore we print currentNode's value and update maxLevelSeenSoFar to level.
       - if left child of currentNode is not null then we add tuple (currentNode.left, level + 1) to 'queue'.
       - if right child of currentNode is not null then we add tuple (currentNode.right, level + 1) to 'queue'.    
       * Please note that we are adding left child of node to the 'queue' before right child to make sure that the left-most node at any level is visited before other nodes at that level.  

After execution of step #4, left view of tree would be printed.

Notice that this algorithm takes O(n) extra space. With the following algorithm, we can save on extra space.

This algorithm basically uses modified pre-order traversal. In this modified pre-order traversal we make sure that -
a. The left-most node of any given level is visited before other nodes in that level. This can be easily achieved by visiting left sub-tree of node before right sub-tree. Basically, in this traversal, we visit the node first, then visit the left sub-tree and finally the right sub-tree(N-L-R).
b. We print out the node value as soon as we encounter a node in the level that is greater than the maximum level seen so far and update maximum level seen so far to current level.

The steps of this algorithm are as following -
1. Initialize maxLevelSeenSoFar to -1 and call printLeftView(currentNode = root, level = 0)
2. In function printLeftView(currentNode, level),
    a. If currentNode is null, then we do nothing and return.
    b. Else, if (level > maxLevelSeenSoFar) we print out the currentNode's value and update maxLevelSeenSoFar to level.
    c. Make a recursive call printLeftView(currentNode.left, level + 1) to make sure nodes in the left sub-tree are visited.
    d. Make a recursive call printLeftView(currentNode.right, level + 1) to make sure nodes in the right sub-tree are visited.    
    ** Notice that while visiting nodes with recursive calls, printLeftView(currentNode.left, level + 1) is called before printLeftView(currentNode.right, level + 1) in order to make sure that for any node, left sub-tree of that node is visited before right sub-tree. This guarantees that at any level, the left-most node is visited before other nodes at that level.

After execution of step #2, left view of tree would be printed.
      
Please checkout code snippet and algorithm visualization section for more details of the algorithm.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.LinkedList;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a binary tree, print the values of nodes which would be present in the left of view of binary tree. 
 * A node will be in the left-view if it is the left most node at its level. 
 * @author Nilesh
 */
public class LeftViewOfBinaryTree {

    class QueueNode
    {
        TreeNode node;
        int level;
        
        QueueNode(TreeNode node, int level)
        {
            this.node = node;
            this.level = level;
        }
    }
    
    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    TreeNode root;

    
    /*
                            1
                      2             3
                  4      5       6  
                    8              9
                      10
    */

    private TreeNode createTree()
    {
        this.root = new TreeNode(1);
        TreeNode n1   = new TreeNode(2);
        TreeNode n2   = new TreeNode(3);
        TreeNode n3   = new TreeNode(4);
        TreeNode n4   = new TreeNode(5);
        TreeNode n5   = new TreeNode(6);
        TreeNode n6   = new TreeNode(8);
        TreeNode n7   = new TreeNode(9);
        TreeNode n8   = new TreeNode(10);
        
        root.left  = n1;
        root.right = n2;
        
        n1.left  = n3;
        n1.right = n4;
        
        n2.left  = n5;
        
        n3.right = n6;
        
        n5.right = n7;
        
        n6.right = n8;
        
        return root;
    }


    int maxLevelSoFar = -1;
    
    public void printLeftViewLevelOrder(TreeNode currentNode)
    {
        if (currentNode == null) return;
        
        LinkedList<QueueNode> queue = new LinkedList();
        
        queue.add(new QueueNode(currentNode, 0));
        
        while (!queue.isEmpty())
        {
            QueueNode queueEntry = queue.remove();
            if (queueEntry.level > maxLevelSoFar)
            {
                maxLevelSoFar = queueEntry.level;
                System.out.println(queueEntry.node.val);
            }
            
            if (queueEntry.node.left != null)
                queue.add(new QueueNode(queueEntry.node.left, queueEntry.level + 1));

            if (queueEntry.node.right != null)
                queue.add(new QueueNode(queueEntry.node.right, queueEntry.level + 1));
        }
        
    }

    
    public void printLeftView(TreeNode currentNode, int currentLevel)
    {
        if (currentNode == null) return;
        
        if (currentLevel > maxLevelSoFar)
        {
            System.out.println(currentNode.val);
            maxLevelSoFar = currentLevel;
        }
        
        printLeftView(currentNode.left, currentLevel + 1);
        printLeftView(currentNode.right, currentLevel + 1);

    }

    public static void main(String[] args)
    {
        LeftViewOfBinaryTree tree = new LeftViewOfBinaryTree();
        
        tree.createTree();
        
        tree.printLeftView(tree.root, 0);
        
        // tree.printLeftViewLevelOrder(tree.root);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer