Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

PrintTopViewofTree.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
104 lines (89 loc) · 2.33 KB
/

PrintTopViewofTree.java

Copy path

File metadata and controls

104 lines (89 loc) · 2.33 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package DataStructures.Trees; // Java program to print top view of Binary tree
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
// Class for a tree node
class TreeNode {
// Members
int key;
TreeNode left, right;
// Constructor
public TreeNode(int key) {
this.key = key;
left = right = null;
}
}
// A class to represent a queue item. The queue is used to do Level
// order traversal. Every Queue item contains node and horizontal
// distance of node from root
class QItem {
TreeNode node;
int hd;
public QItem(TreeNode n, int h) {
node = n;
hd = h;
}
}
// Class for a Binary Tree
class Tree {
TreeNode root;
// Constructors
public Tree() {
root = null;
}
public Tree(TreeNode n) {
root = n;
}
// This method prints nodes in top view of binary tree
public void printTopView() {
// base case
if (root == null) {
return;
}
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Create a queue and add root to it
Queue<QItem> Q = new LinkedList<QItem>();
Q.add(new QItem(root, 0)); // Horizontal distance of root is 0
// Standard BFS or level order traversal loop
while (!Q.isEmpty()) {
// Remove the front item and get its details
QItem qi = Q.remove();
int hd = qi.hd;
TreeNode n = qi.node;
// If this is the first node at its horizontal distance,
// then this node is in top view
if (!set.contains(hd)) {
set.add(hd);
System.out.print(n.key + " ");
}
// Enqueue left and right children of current node
if (n.left != null) Q.add(new QItem(n.left, hd - 1));
if (n.right != null) Q.add(new QItem(n.right, hd + 1));
}
}
}
// Driver class to test above methods
public class PrintTopViewofTree {
public static void main(String[] args) {
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.left.right.right = new TreeNode(5);
root.left.right.right.right = new TreeNode(6);
Tree t = new Tree(root);
System.out.println("Following are nodes in top view of Binary Tree");
t.printTopView();
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.