Print right view of a binary tree

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

Approach

For printing the right 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 rightmost 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 = 0; i < n; i++) {
                Node temp = queue.poll();


                if (i == n - 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("Right view of Given Tree: ");
        tt.printLeftView(tt.root);

    }

}

Output

Right view of Given Tree:
1 3 6