Print left view of a binary tree


In this program we want to print the left view of a binary tree. Imagine you are viewing the binary tree from the left side, you would only see the nodes that are on the left side. Any nodes that are at the same level but not on the extreme left will not be visible. 

 

Approach

For printing the left view of a given binary tree, we have to use level order traversal using queue data structure.

We have traversed each level of the binary tree and printed its leftmost node data.

 

Algorithm

  1. If root is NULL then simply return.
  2. Create Queue, say queue and add root into it.
  3. While the queue is not empty, store size(total nodes on current  of queue in variable say ‘n’.
  4. Traverse all nodes of current level using for loop.
  5. Remove elements from the queue and store into temp.
  6. If i==1 the  print that node data ( we got left most nodes of that level).
  7. If temp.left is not NULL then add temp.left in the queue.
  8. If temp.right  is not NULL then add temp.right in the queue.

 

Complexity

  • Time Complexity : O(n) , where n is the number of nodes in a binary tree.
  • Space Complexity : O(n), where n is the number of nodes in a binary tree.

 

Java code
import java.util.LinkedList;

import java.util.Queue;


class Node {

    int data;

    Node left, right;


    Node(int element) {

        data = element;

        left = right = null;

    }

}


class binaryTree{

    Node root;


    public static Node constructBinaryTree(int[] arr, int i) {

        Node root = null;

        if (i < arr.length) {

            root = new Node(arr[i]);

            root.left = constructBinaryTree(arr, 2 * i + 1);

            root.right = constructBinaryTree(arr, 2 * i + 2);

        }

        return root;
    }


    public void printLeftView(Node root) {

        if (root == null)

            return;


        Queue<Node> queue = new LinkedList<>();

        queue.add(root);


        while (!queue.isEmpty()) {

            int n = queue.size();


            for (int i = 1; i <= n; i++) {

                Node temp = queue.poll();

                if (i == 1)

                    System.out.print(temp.data + " ");


                if (temp.left != null)

                    queue.add(temp.left);

                if (temp.right != null)

                    queue.add(temp.right);

           }
        }
    }


    public static void main(String args[]) {

        binaryTree tt = new binaryTree();

        int[] bstElements = new int[] { 1, 2, 3, 4, 5, 6 };

        tt.root = constructBinaryTree(bstElements, 0);

        System.out.println("Left view of Given Tree: ");

        tt.printLeftView(tt.root);

    }

}

 

Output

Left view of Given Tree:

1 2 4

 



Thanks for feedback.



Read More....
Check if a binary tree is a min heap
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Iterative approach
Create a mirror of binary tree - Recursive approach
Find the height of binary tree - Iterative approach