Print Left View Of Binary Tree

Problem Statement

Given a Binary Tree, print left view of binary tree. Left view of Binary Tree is set of nodes visible when tree is visited from left side.

Example:

Output: 1 2 4 8

Problem Explanation

First, let’s understand what exactly is the left side of binary tree? Take a look at the image above and the person can see the nodes that are on the left side of the tree. In simpler terms I could say that it is the first element of each one of the layers.

Level 0: 1 Level 1: 2 Level 2: 4. Level 3: 8

Left View Of Binary Tree Solution

Method 1: Recursion

The problem can be solved with a simple preorder traversal using recursion. Idea is to keep track of the node’s level by sending a parameter to all Recursive calls. The goal is to track the highest level as well. If we come across any node with a level greater than its maximum level, we print the node since this is the first node of its level.

Algorithm:

• Do a preorder the traversal in the Tree
• Check if this node is first from its level by comparing max level visited so far with level of node
• If its first node print the node and update max level visited so far to current node
• Since we want left view, we will Move to the left child first and increase your level one
• Move to the right and keep increasing the level.

Implementation:

// Java program to print left view of binary tree

class Node {
    int data;
    Node left, right;
    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class LeftViewOfBinaryTree {
    //Variable to keep track of maximum level visited so far
    static int maxLevelVisitedSoFar = 0;

    // recursive function to print left view using preoroder
    static void leftViewOfBinaryTree(Node node, int level) {
        // Base Case
        if (node == null)
            return;

        // If this is the first node of its level
        if (maxLevelVisitedSoFar < level) {
            System.out.print(" " + node.data);
            maxLevelVisitedSoFar = level;
        }

        // Recur for left and right subtrees incrementing the level
        leftViewOfBinaryTree(node.left, level + 1);
        leftViewOfBinaryTree(node.right, level + 1);
    }

    public static void main(String args[]) {
        // creating a binary tree and entering the nodes
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.right.left = new Node(7);
        root.right.right.left = new Node(8);
        root.right.right.right = new Node(9);

        leftViewOfBinaryTree(root, 1);
    }
}

Time Complexity:  O(n). 
Auxiliary Space: O(n), due to the stack space during recursive call.

Method 2: Iterative Using Queue

In this method, we will use level order traversal to print left view of binary tree. Since our main objective is to find the left most node of every level so by using a simple level order traversal we will print the leftmost node at every level. For this, we’ll use queue to store all the nodes in the current level.

Algorithm:

1. Perform level order traversal.
2. Print the first node at each level in the tree and push the children of all nodes at each level in the queue.
3. Repeat the above steps till queue becomes empty.

Implementation:

// Java program to print left view of binary tree

import java.util.*;

class Node {
    int data;
    Node left, right;
    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class LeftViewOfBinaryTree {
    static void leftViewOfBinaryTree(Node node, int level) {
        // base case
        if (node == null)
            return;

        // Queue for level order traversal   
        Queue < Node > queue = new LinkedList < > ();
        queue.add(node);

        while (!queue.isEmpty()) {
            // Calculate number of nodes at current level
            int n = queue.size();

            // Traverse all nodes of current level
            for (int i = 1; i <= n; i++) {
                Node temp = queue.poll();

                // Print the left most/First node of the current level
                if (i == 1)
                    System.out.print(temp.data + " ");

                // Add left node to queue
                if (temp.left != null)
                    queue.add(temp.left);

                // Add right node to queue
                if (temp.right != null)
                    queue.add(temp.right);
            }
        }
    }

    public static void main(String args[]) {
        // creating a binary tree and entering the nodes
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.right.left = new Node(7);
        root.right.right.left = new Node(8);
        root.right.right.right = new Node(9);

        leftViewOfBinaryTree(root, 1);
    }
}

Time Complexity:  O(n). 
Auxiliary Space: O(n), for maintaining queue.

Conclusion

In this post we discussed iterative and recursive way to print left view of binary tree.

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!