Types of View Algorithms — Binary Tree

Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children.

Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to an arbitrary number of nodes, called children.

In this article, we will look into various view algorithms of the binary tree and we will discuss each and every algorithm with a common pattern with some twist and twigs of some line of code. 🙌

We will first understand one algorithm intuitive by which we will create a template and solve all other problems.

Types of View in Binary Tree are :

1. Horizontal View
2. Vertical View
3. Left View
4. Right View
5. Top View
6. Bottom View

Horizontal View: Let first understand the Horizontal View of Binary Tree or Level Order View.

A Tree is represented by at most two children left and right. First of all, we know that can be traversed a tree by BFS(Queue) or DFS(Stack) in the problem statement it is mentioned about Level Order so What can we use BFS or DFS?

BFS right!! So we can use the Queue data structure for storing the node value as simple as that. So the root will be at level 0 and below that root right and root left will be at level 1 and so forth and so on….

We need to store Node and Level in a queue so we can use a Pair Data structure to store value in pairs. First, we will store the root node value and level as 0 into the queue. We will iterate until the queue is not empty and we will store the left and right child node and (level +1) into the queue each time. We will add the node value into the ArrayList at a certain level.

So as you have looked in the above code to better understand the concept we have created this as a template for all other problems.

The Overall Time Complexity is O(N )and Space Complexity is O(N)

Right View: If you can see the tree from the right side all the nodes that's are ending node of each list. As we have understand how to solve a problem for the Horizontal view we will use the template and add a few lines of code to solve this problem.

In the above code, we need to iterate through the ArrayList of Horizontal View and get the last value from each List and add to the new ArrayList.

Left View: If you can see the tree from the left side all the nodes are starting node of each list. In the above code, we need to iterate through the ArrayList of Horizontal View and get the first value from each List and add to the new ArrayList.

Bottom View: If you can see the tree from the bottom for a Full Binary Tree the last list from the Horizontal View is the bottom view.

Top View: From the above implementation if you can think of looking from the top of the tree you will see every outmost and innermost node at each level. Iterating through the ArrayList of Horizontal View and getting the first and last value of each list except the root value. Where root value is only one element in the tree so we can insert the root.

Vertical View: Let understand this as it is a little different problem from all the problem that we have done till now. Let recall that in Horizontal View we took root as level 0 and root.right and root.left as level 1 and so forth and so on ….The idea is root will be level 0 but root.right will have a (currentlevel+1) and root.left will be (currentlevel-1) and store this in the list.

Think wisely which data structure we can use to solve this problem ??

The Map data structure can be used Right !!!! we can store a key as level and values as ArrayList.

The Concept is same but little change we have to use the map to store vertical view list.

So I hope you had understood the basic concept of View Algorithms to solve any view related problem of the binary tree.

Please let me know in the comment below what is your opinion about these algorithms.