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