FilesExpand file tree

 master

/

PrintTopViewofTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

104 lines (89 loc) · 2.33 KB

 master

/

PrintTopViewofTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

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();

}

}