Top and Bottom View of Binary Tree

In this article, we will print the top and bottom view of a binary tree. For this, we need to perform vertical order traversal on the tree and then we can easily find out the top and bottom view of it.

We can either use recursion or a Queue based traversal of a binary tree for vertical order traversal and in this article, we will be using recursion for the same.

The top view of a binary tree consists of all the nodes that are visible when we see a tree from the top and similarly the bottom view consists of all the nodes that are visible from the bottom end.

Below is a sample binary tree for which we will find the top and bottom view.

Top View - 5 7 14 10 15
Bottom View - 14 7 30 25 15

If we draw the tree properly, the node with value 19 and 30 will overlap on each other and hence in the output we print any one of the overlapping nodes and here we are printing 30.

Vertical Order Traversal

Below is a pictorial representation of vertical order traversal of a binary tree. Any one of the nodes in each vertical representation can be viewed in the top and bottom view of the tree.

Assuming the root node to be at a horizontal distance of 0, we decrease the left node hd by 1 and increase the right node hd by 1 in comparison to its parent node. Based on this distance, we have divided it vertically.

Below is the algorithm for vertical order traversal.

For root 
	hd = 0;

For left child
	hd = hd-1;

For right child
	hd = hd + 1;

Algorithm for Top View of Binary Tree

While performing level order traversal, we will store the node in a Map in which the key would be the horizontal distance of a particular node and the values will be the list of nodes present at that distance.

public class VerticalOrderTraversal {

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

    public static void verticalOrderTraversalRecursive(BinaryTreeNode root, int weight){
        if(root == null){
            return;
        }
        putToMap(weight, root);
        verticalOrderTraversalRecursive(root.getLeftNode(), weight - 1);
        verticalOrderTraversalRecursive(root.getRightNode(), weight + 1);
    }

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

     public static void main(String[] args){

     }

}

Now, let us print the content of our map and then try to extract the top and bottom view out of it.

public static void main(String[] args){
        BinaryTree tree = new BinaryTree();
        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));
        VerticalOrderTraversal.verticalOrderTraversalRecursive(root, 0);
        for (Map.Entry<Integer, List<BinaryTreeNode>> entry: map.entrySet()){
            System.out.print(entry.getKey() + ": ");
            entry.getValue().forEach(val -> System.out.print(val.getData() + " "));
            System.out.println();
        }
    }

-2: 14 
-1: 7 
0: 5 19 30 
1: 10 25 
2: 15 

Now, if we see the output, we can easily identify the top view of the tree. All the first node of each horizontal distance is the top view. Hence the top view becomes 14 7 5 10 15

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

Bottom View of Binary Tree

The bottom view of the binary tree would be the last element of the list for each horizontal distance - 14 7 30 25 15. If we draw the tree properly, the node with values 19 and 30 will overlap on each other and hence in the output, we print any one of the overlapping nodes and here we are printing 30.

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

Conclusion

In this article, we implemented the algorithm to print the top and bottom view of a binary tree with vertical level traversal of a tree.