Print Nodes in Top View of Binary Tree
Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. Expected time complexity is O(n)
A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.
1
/ \
2 3
/ \ / \
4 5 6 7
Top view of the above binary tree is
4 2 1 3 7
1
/ \
2 3
\
4
\
5
\
6
Top view of the above binary tree is
2 1 3 6
The idea is to do something similar to vertical Order Traversal. Like vertical Order Traversal, we need to put nodes of same horizontal distance together. We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. Hashing is used to check if a node at given horizontal distance is seen or not.
C++
// C++ program to print top // view of binary tree � �#include <iostream>� #include<queue>� #include<map> using namespace std; � �// Structure of binary tree struct Node { ���� Node * left; ���� Node* right; ���� int hd; ���� int data; }; � �// function to create a new node Node* newNode( int key) { ���� Node* node= new Node(); ���� node->left = node->right = NULL; ���� node->data=key; ���� return node; } � �// function should print the topView of // the binary tree void topview(Node* root) { ���� if (root==NULL) ������� return ; ����� queue<Node*>q; ����� map< int , int > m;� ����� int hd=0; ����� root->hd=hd; ������ ������ // push node and horizontal distance to queue ���� q.push(root); ����� ����� cout<< "The top view of the tree is : \n" ; ����� ����� while (q.size()) ���� { �������� hd=root->hd; ��������� ��������� // count function returns 1 if the container� �������� // contains an element whose key is equivalent� �������� // to hd, or returns zero otherwise. �������� if (m.count(hd)==0)�� �������� m[hd]=root->data; �������� if (root->left) �������� { ������������ root->left->hd=hd-1; ������������ q.push(root->left); �������� } �������� if (root->right) �������� { ������������ root->right->hd=hd+1; ������������ q.push(root->right); �������� } �������� q.pop(); �������� root=q.front(); ������� ����� } ����� ������ ������ ������ for ( auto i=m.begin();i!=m.end();i++) ���� { �������� cout<<i->second<< " " ; ���� } ����� �} �� �// Driver Program to test above functions int main() { ���� /* Create following Binary Tree� ������������ 1� �������� / \� �������� 2 3� �������� \� ������������ 4� ������������ \� ������������ 5� ������������ \� ���������������� 6*/ ��� Node* root = newNode(1); ���� root->left = newNode(2); ���� root->right = newNode(3); ���� root->left->right = newNode(4); ���� root->left->right->right = newNode(5); ���� root->left->right->right->right = newNode(6); ���� cout<< "Following are nodes in top view of Binary Tree\n" ;� ���� topview(root); ���� return 0; } /* This code is contributed by Niteesh Kumar */ |
chevron_right
filter_none
Java
// Java program to print top // view of binary tree 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 = right = null ; ���� } } � �// class of binary tree class BinaryTree { ���� Node root; � ����� public BinaryTree() { �������� root = null ; ���� } ����� ����� // function should print the topView of ���� // the binary tree ���� private void TopView(Node root) { �������� class QueueObj { ������������ Node node; ������������ int hd; � ������������� QueueObj(Node node, int hd) { ���������������� this .node = node; ���������������� this .hd = hd; ������������ } �������� } �������� Queue<QueueObj> q = new LinkedList<QueueObj>(); �������� Map<Integer, Node> topViewMap = new TreeMap<Integer, Node>(); � ��������� if (root == null ) { ������������ return ; �������� } else { ������������ q.add( new QueueObj(root, 0 )); �������� } � ��������� System.out.println( "The top view of the tree is : " ); ��������� ��������� // count function returns 1 if the container� �������� // contains an element whose key is equivalent� �������� // to hd, or returns zero otherwise. �������� while (!q.isEmpty()) { ������������ QueueObj tmpNode = q.poll(); ������������ if (!topViewMap.containsKey(tmpNode.hd)) { ���������������� topViewMap.put(tmpNode.hd, tmpNode.node); ������������ } � ������������� if (tmpNode.node.left != null ) { ���������������� q.add( new QueueObj(tmpNode.node.left, tmpNode.hd - 1 )); ������������ } ������������ if (tmpNode.node.right != null ) { ���������������� q.add( new QueueObj(tmpNode.node.right, tmpNode.hd + 1 )); ������������ } � ��������� } �������� for (Entry<Integer, Node> entry : topViewMap.entrySet()) { ������������ System.out.print(entry.getValue().data); �������� } ���� } ����� ����� // Driver Program to test above functions ���� public static void main(String[] args)� ���� {� �������� /* Create following Binary Tree� ������������ 1� �������� / \� �������� 2 3� �������� \� ������������ 4� ������������ \� ������������ 5� ������������ \� ���������������� 6*/ �������� BinaryTree tree = new BinaryTree(); �������� tree.root = new Node( 1 ); �������� tree.root.left = new Node( 2 ); �������� tree.root.right = new Node( 3 ); �������� tree.root.left.right = new Node( 4 ); �������� tree.root.left.right.right = new Node( 5 ); �������� tree.root.left.right.right.right = new Node( 6 ); �������� System.out.println( "Following are nodes in top view of Binary Tree" );� �������� tree.TopView(tree.root);� ���� }� ����� �} |
chevron_right
filter_none
Output:
Following are nodes in top view of Binary Tree
2136
Time Complexity of the above implementation is O(n) where n is the number of nodes in the given binary tree. The assumption here is that add() and contains() methods of HashSet work in O(1) time.
This article is contributed by Rohan. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Recommended Posts:
- Print nodes in top view of Binary Tree | Set 2
- Print nodes in the Top View of Binary Tree | Set 3
- Print Right View of a Binary Tree
- Print Left View of a Binary Tree
- Print all nodes between two given levels in Binary Tree
- Print all full nodes in a Binary Tree
- Print all nodes in a binary tree having K leaves
- Print path between any two nodes in a Binary Tree
- Print Levels of all nodes in a Binary Tree
- Print all even nodes of Binary Search Tree
- Print nodes between two given level numbers of a binary tree
- Print the nodes of binary tree as they become the leaf node
- Print leftmost and rightmost nodes of a Binary Tree
- Print all leaf nodes of a Binary Tree from left to right
- Print Sum and Product of all Non-Leaf nodes in Binary Tree
No comments:
Post a Comment