Left and Right View of Binary Tree in Java

In the last article, we learned multiple ways of Level Order Traversal of a binary tree. In this article, we will use that technique to print the left and right view of a binary tree with level order traversal by using the Queue data structure.

Below is the binary tree that will be used for printing the left view of it. The nodes which are highlighted represents the left view of the tree.

Left view of the tree contains all the nodes that can be viewed while viewing a tree from its left side. Below are the nodes that form left view of the tree.

5 
7
14
25

When we analyze it, it is basically all the leftmost nodes of a level order traversal of a binary tree. Below is the level order traversal of the binary tree for above binary tree.

5
7 10
14 19 30 15
25

Hence, we can print the left view of a tree if we can print the first position node of every level of a binary tree.

There are multiple ways of level order traversal of a binary tree. Either we can use recursion or we can use Queue for level order traversing. We have discussed 3 ways of level order traversal in our last article here.

Algorithm for Binary Tree Left View

For this particular problem we will be using a Queue for tree traversal and a Map to store the level order nodes where the key of the Map will be the level of the tree and the values will be the list of nodes present at the corresponding level.

Below is the algorithm for the same.

enqueue root
enqueue null
while queue is not empty
	node = dequeue queue
	if node is null
		increase level
		enqueue null again //meaning one level of nodes already enqueued
	else
		enqueue left and right child of node
		 

Java Program for Binary Tree Left View

Below is the node class implementation.

public class BinaryTreeNode {

    private int data;
    private BinaryTreeNode leftNode;
    private BinaryTreeNode rightNode;

//setters and gettters

The method levelOrderTraversal() accepts the root of the tree. We have a static map declared to store the level wise tree node. We can either use LinkedHashMap or TreeMap implementation of it.

We have an extra variable declaration as removalCount to keep track of our null count. We will exit the loop once this counter variable value exceeds 2 meaning there are no more elements in the queue to process.

public class TreeLeftView {

    static Map<Integer, List<BinaryTreeNode>> map = new TreeMap<>();

    public static void levelOrderTraversal(BinaryTreeNode root){
        int level = 0; int removalCount = 0;
        Queue<BinaryTreeNode> queue = new LinkedList>();
        queue.add(root);
        queue.add(null);
        while (!queue.isEmpty()){
            BinaryTreeNode node = queue.poll();
            if (node == null){
                //when we encounter null meaning one level of trabersal is completed. Hence increase the level
                removalCount = removalCount + 1;
                if (removalCount > 1){
                    break;
                }
                queue.add(null);
                level = level + 1;
            }else {
                removalCount = 0;
                if (node.getLeftNode() != null) {
                    queue.add(node.getLeftNode());
                }
                if (node.getRightNode() != null) {
                    queue.add(node.getRightNode());
                }
                populateMap(level, node);
            }
        }
        printLeftView();
    }
}

Below is the implementation to populate the map. While adding the first node of any level, we first create an entry in the Map witth key as the level of the tree and an empty list as its value.

private static void populateMap(int level, BinaryTreeNode node) {
        List<BinaryTreeNode> nodes = map.get(level);
        if (nodes == null){
            nodes = new ArrayList<>();
        }
        nodes.add(node);
        map.put(level, nodes);
    }

To print the left view of the tree, we can simply traverse the map and print the first element of the list of every level.

private static void printLeftView() {
        for (Map.Entry<Integer, List<BinaryTreeNode>> entry: map.entrySet()){
            System.out.println(entry.getValue().get(0).getData());
        }
    }

we can use the same map to print the right view.

private static void printRightView() {
        for (Map.Entry<Integer, List<BinaryTreeNode>> entry: map.entrySet()){
            System.out.println(entry.getValue().get(entry.getValue().size() - 1).getData());
        }
    }

Tree Runner

We have a main method that constructs the tree as per above tree diagram.

public static void main(String[] args){
        BinaryTreeNode root = new BinaryTreeNode(5);
        root.setLeftNode(new BinaryTreeNode(7));
        root.setRightNode(new BinaryTreeNode(10));
        root.getLeftNode().setLeftNode(new BinaryTreeNode(14));
        root.getLeftNode().setRightNode(new BinaryTreeNode(19));

        root.getRightNode().setLeftNode(new BinaryTreeNode(30));
        root.getRightNode().setRightNode(new BinaryTreeNode(15));

        root.getRightNode().getRightNode().setLeftNode(new BinaryTreeNode(25));
        TreeLeftView.levelOrderTraversal(root);
    }

Conclusion

In this article, we implemented the algorithm to print the left view of a binary tree in Java.