• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jul 22nd, 2019 56 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top