Print the left view of a binary tree

Given a binary tree the left view of it would be the first node at each level from the left or the last node at each from the right.

Example

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

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

Left view of binary tree

We are going to see the iterative as well as recursive solution for it.

Recursively print the left view of binary tree

We are to use the level order traversal to print the first node at each level in the tree.

  • Use an external variable to track the level.
  • If the variable value is less than the current level that means we just moved to the new level, so print it’s first element.
let max_level = 0;
const leftViewRecursive = (node, level) => {
  if(node === null){
    return;
  }
  
  if(max_level < level){
    console.log(node.val);
    max_level = level;
  }
  
  leftViewRecursive(node.left, level+1);
  leftViewRecursive(node.right, level+1);
}
Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

let tree = new Node(4);  
tree.left = new Node(5); 
tree.right = new Node(2); 
tree.left.left = new Node(3); 
tree.left.right = new Node(1);
tree.right.right = new Node(6);

leftViewRecursive(tree, 1);

Output:
4
5
3

Time complexity: O(n).
Space complexity: O(n).


Iterative way to print the left view of a tree.

We are going to use queue to perform the level order traversal and then print the first node at each level.

Here I have used an array as a queue but you can do vice-versa.

const leftViewIterative = (node) => {
  if(node === null){
    return;
  }
  
  let q = [];
  
  q.unshift(node);
  
  q.unshift(null);
  
   while (q.length > 0)  
    { 
        let temp = q[q.length - 1]; 
  
        if (temp !== null) 
        { 
  
            // Prints first node 
            // of each level 
            console.log(temp.val); 
  
            // add children of all nodes at 
            // current level 
            while (q[q.length - 1] !== null) 
            { 
                // If left child is present 
                // add into queue 
                if (temp.left !== null) 
                    q.unshift(temp.left); 
  
                // If right child is present 
                // add into queue 
                if (temp.right !== null) 
                    q.unshift(temp.right); 
  
                // remove the current node 
                q.pop(); 
  
                temp = q[q.length - 1]; 
            } 
  
            // add delimiter 
            // for the next level 
            q.unshift(null); 
        } 
  
        // remove the delimiter of 
        // the previous level 
        q.pop(); 
    } 
  
}
Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

let tree = new Node(4);  
tree.left = new Node(5); 
tree.right = new Node(2); 
tree.left.left = new Node(3); 
tree.left.right = new Node(1);
tree.right.right = new Node(6);
leftViewIterative(tree);

Output:
4
5
3

Time complexity: O(n).
Space complexity: O(n).