Given a binary tree we have to print top view. We will discuss our approach to solve this problem along with its implementation and code in Java language. We will also analyze the time and space complexity of our implementation.
The top view of binary tree means the set of nodes visible when the tree is viewed from top. In other words, a node is included in our top view if it is the topmost node at it’s respective horizontal distance.
We calculate the horizontal distance as follows:
- The Horizontal Distance of Root of tree=0.
- Horizontal Distance of Left Child=Horizontal Distance of it’s Parent Node – 1.
- The Horizontal Distance of Right Child=Horizontal Distance of it’s Parent Node + 1.
Let us consider binary tree give below:
The top view of this tree will give output: 2 1 3 6.
Explanation:
The nodes are highlighted in the figure above. We put nodes with same horizontal distance together. We start from the root node 1 at level 1 the horizontal distance is 0 at root, then we go down each level and print the topmost node for that horizontal distance. At level 2 node 2 is the topmost node with horizontal distance -1 so print it, at the same level 2 node 3 is the topmost node with horizontal distance 1. At level 3 node 6 is the topmost node with horizontal distance 2.
Input: // Tree is Viewed from top here hd=Horizontal distance
hd=0 20 -- level 1
/ \
/ \
hd=-1 10 30 hd= +1 -- level 2
/ \ / \
/ \ / \
hd=-2 5 15 25 35 hd= +2 -- level 3
hd=0 hd=0
Output: 5 10 20 30 35
Approach (Using Level Order Traversal and Hashing)
The idea of our approach is to put nodes with same horizontal distance together. Then, print the topmost node with the respective horizontal distance. We get the topmost node by maintaining a map and doing level order traversal. At a particular level if the node with the given horizontal distance is not present in our map, we add the node’s hd as a key to our map and it’s data as the value. We maintain a pair class of node and hd to maintain each node’s hd and level in our Queue while processing them. We add a given hd only once which ensures only the topmost node is present in our map. Lastly, we print the values of the map. In order to print the top view from left to right we use a Tree Map to order the Map with respect to hd.
Note: We use the short form of horizontal distance of each node as hd.
Below is the implementation in Java:
import java.util.Queue;
import java.util.TreeMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
// class to create a node
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class NodeObj // Each Object holds the current node to add in Queue
{
Node node;
int hd; // Horizontal Distance of each Node
NodeObj(Node node, int hd)
{
this.node = node;
this.hd = hd;
}
}
// class of binary tree
public class Tree
{
Node root;
// method to print the topView of the binary tree
void TopView(Node root)
{
if (root == null)
return; // There is no top view of of a tree having root null
Queue<NodeObj> queue = new LinkedList<NodeObj>();
// Declare Map to maintain hd and node data.
Map<Integer,Integer> topView = new TreeMap<>();
// We first add the root into the queue along with it's hd 0.
queue.add(new NodeObj(root, 0));
// Standard level order traversal using Queue
while (!queue.isEmpty())
{
NodeObj curr = queue.poll(); // we dequeue the curent NodeObj
Node tempNode=curr.node; // get the current node to process.
int hd=curr.hd; // get the node's respective horizontal distance.
// if our map does not contain the current node's hd we insert it.
if (!topView.containsKey(hd))
{
topView.put(hd,tempNode.data);
}
// Now add the left and right child of each node
// to continue level order traversal
if (tempNode.left != null)
{
// hd of left child = hd of parent node - 1.
queue.add(new NodeObj(tempNode.left, hd - 1));
}
if (tempNode.right != null)
{
// hd of right child = hd of parent node + 1.
queue.add(new NodeObj(tempNode.right, hd + 1));
}
}
// We just print the values corresponding to each key(hd) or the nodes present in top view
for (Entry<Integer, Integer> entry : topView.entrySet()) {
System.out.print(entry.getValue()+" ");
}
}
// Driver Code or Main method to test above functions
public static void main(String[] args)
{
Tree tree = new Tree();
tree.root = new Node(20);
tree.root.left = new Node(10);
tree.root.left.left = new Node(5);
tree.root.left.right = new Node(15);
tree.root.right = new Node(30);
tree.root.right.left = new Node(25);
tree.root.right.right = new Node(35);
System.out.println("The Top View of Binary Tree is: ");
tree.TopView(tree.root);
}
}
Output:
The Top View of Binary Tree is: 5 10 20 30 35
Time Complexity: Now we analyze the time complexity of our approach. We do a level order traversal of all the nodes in O (n). Along with this, and each insertion in our Tree-Map takes O (log n) time. So the Overall time Complexity will be O (n*log n).
Space Complexity: The Queue we use to implement the level order traversal will at the most store the nodes present at all levels and if we are given a skewed binary tree then it will store nodes at all levels so the overall space complexity is O (n).
That’s it for the Top View of Binary tree you can try this approach and run the code in your IDE or Java compiler.
You can ask your queries in the comment section below.