Untitled

a guest
Jul 22nd, 2019
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Horizontal distance(hd) of root = 0
2. If you go left then hd = hd(of its parent)-1, and
3. if you go right then hd = hd(of its parent)+1.
4.
5. 1
6. /
7. 2 3
8. / /
9. 4 5 6 7
10.
11. 8
12.
13. Ok so for the first example,
14. Horizontal distance of node with value 1: 0, level = 1
15. Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
16. Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
17. Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
18. Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
19. Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
20. Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
21. Horizontal distance of node with value 8: 0 + 1 = 1, level = 4
22.
23. So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
24. So for hd = -2, print 4
25. for hd = -1, print 2
26. for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
27. for hd = 1, print 8
28. for hd = 2, print 7
29.
30. 1
31. /
32. 2 3
33. / /
34. 4 5 6 7
35. / / / /
36. 8 9 10 11 12 13 14 15
37.
38. Similarly for this example
39. hd of node with value 1: 0, , level = 1
40. hd of node with value 2: -1, level = 2
41. hd of node with value 3: 1, level = 2
42. hd of node with value 4: -2, level = 3
43. hd of node with value 5: 0, , level = 3
44. hd of node with value 6: 0, level = 3
45. hd of node with value 7: 2, level = 3
46. hd of node with value 8: -3, level = 4
47. hd of node with value 9: -1, level = 4
48. hd of node with value 10: -1, level = 4
49. hd of node with value 11: 1, level = 4
50. hd of node with value 12: -1, level = 4
51. hd of node with value 13: 1, level = 4
52. hd of node with value 14: 1, level = 4
53. hd of node with value 15: 3, level = 4
54.
55. So, the output will be:
56. hd = -3, print 8
57. hd = -2, print 4
58. hd = -1, print 9 10 12
59. hd = 0, print 5 6
60. hd = 1, print 11 13 14
61. hd = 2, print 7
62. hd = 3, print 15
63.
64. So the ouput will be:
65. 8 4 9 10 12 5 6 11 13 14 7 15
66.
67. void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
68. {
69. if(node == NULL)
70. return;
71. if(level == 1){
72. if(lev[hd-min] == 0 || lev[hd-min] == l){
73. lev[hd-min] = l;
74. visited[hd-min].push_back(node->data);
75. }
76. }
77. else if(level > 1)
78. {
79. printBottom(node->left, level-1, hd-1, min, visited, lev, l);
80. printBottom(node->right, level-1, hd+1, min, visited, lev, l);
81. }
82. }
83.
84.
85. int main()
86. {
87. find the minimum and maximum values for hd via DFS
88.
89. int lev[max-min+1]; //lev[hd] contains the maximum level for which we have found nodes with this value of hd; initialized with 0's
90.
91. map < int, vector<int> > visited; //the nodes in the bottom view
92.
93. int h = height(root);
94.
95. for (int i=h; i>0; i--){
96. printBottom(root, i, 0, min, visited, lev, i);
97. }
98.
99. output visited
100. }
101.
102. void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
103. {
104. if(node == NULL)
105. return;
106. if(lev[hd-min] < level){
107. lev[hd-min] = level;
108. visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
109. }
110. if(lev[hd-min] <= level){
111. visited[hd-min].push_back(node->data);
112. }
113. printBottom(node->left, level+1, hd-1, min, visited, lev);
114. printBottom(node->right, level+1, hd+1, min, visited, lev);
115. }
116.
117. void fillLev(Node *node, int level, int hd, int min, int lev[])
118. {
119. if(node == NULL)
120. return;
121. if(lev[hd-min] < level){
122. lev[hd-min] = level;
123. }
124. fillLev(node->left, level+1, hd-1, min, lev);
125. fillLev(node->right, level+1, hd+1, min, lev);
126. }
127. void printBottom(Node *node, int level, int hd, int min, int lev[])
128. {
129. if(node == NULL)
130. return;
131. if(lev[hd-min] == level){
132. cout << node->data;
133. }
134. printBottom(node->left, level+1, hd-1, min, lev);
135. printBottom(node->right, level+1, hd+1, min, lev);
136. }
137.
138. public class node
139. {
140. public int data;
141. public node left, right;
142. public int hd;
143. };
144.
145. // A utility function to create a new
146. // Binary Tree node
147. static node newNode(int item)
148. {
149. node temp = new node();
150. temp.data = item;
151. temp.left = null;
152. temp.right = null;
153. return temp;
154. }
155.
156. static void rightViewOfBT(node root)
157. {
158. Queue<node> queue = new Queue<node>();
159. SortedDictionary<int, int> treeMap = new SortedDictionary<int, int>();
160. int hd = 0;
161. root.hd = hd;
162. queue.Enqueue(root);
163. while(queue.Count > 0)
164. {
165. node temp = queue.Peek();
166. queue.Dequeue();
167.
168. if (treeMap.ContainsKey(temp.hd))
169. {
170. treeMap[temp.hd] = temp.data;
171. }
172. else
173. {
175. }
176.
177. if (temp.left != null)
178. {
179. temp.left.hd = temp.hd - 1;
180. queue.Enqueue(temp.left);
181. }
182.
183. if (temp.right != null)
184. {
185. temp.right.hd = temp.hd + 1;
186. queue.Enqueue(temp.right);
187. }
188. }
189. foreach (var tree in treeMap)
190. Console.Write(tree.Value);
191. }
192.
193. static void Main(string[] args)
194. {
195. node root = newNode(1);
196. root.left = newNode(2);
197. root.right = newNode(3);
198. root.left.left = newNode(4);
199. root.left.right = newNode(5);
200. root.left.left.right = newNode(8);
201. root.left.right.left = newNode(9);
202. root.right.left = newNode(6);
203. root.right.right = newNode(7);
204. root.right.right.right = newNode(11);
205. root.right.left.right = newNode(10);
206. rightViewOfBT(root);
207. }
RAW Paste Data