Guest User

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. {
  174. treeMap.Add(temp.hd, temp.data);
  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