Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Horizontal distance(hd) of root = 0
- If you go left then hd = hd(of its parent)-1, and
- if you go right then hd = hd(of its parent)+1.
- 1
- /
- 2 3
- / /
- 4 5 6 7
- 8
- Ok so for the first example,
- Horizontal distance of node with value 1: 0, level = 1
- Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
- Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
- Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
- Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
- Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
- Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
- Horizontal distance of node with value 8: 0 + 1 = 1, level = 4
- So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
- So for hd = -2, print 4
- for hd = -1, print 2
- for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
- for hd = 1, print 8
- for hd = 2, print 7
- 1
- /
- 2 3
- / /
- 4 5 6 7
- / / / /
- 8 9 10 11 12 13 14 15
- Similarly for this example
- hd of node with value 1: 0, , level = 1
- hd of node with value 2: -1, level = 2
- hd of node with value 3: 1, level = 2
- hd of node with value 4: -2, level = 3
- hd of node with value 5: 0, , level = 3
- hd of node with value 6: 0, level = 3
- hd of node with value 7: 2, level = 3
- hd of node with value 8: -3, level = 4
- hd of node with value 9: -1, level = 4
- hd of node with value 10: -1, level = 4
- hd of node with value 11: 1, level = 4
- hd of node with value 12: -1, level = 4
- hd of node with value 13: 1, level = 4
- hd of node with value 14: 1, level = 4
- hd of node with value 15: 3, level = 4
- So, the output will be:
- hd = -3, print 8
- hd = -2, print 4
- hd = -1, print 9 10 12
- hd = 0, print 5 6
- hd = 1, print 11 13 14
- hd = 2, print 7
- hd = 3, print 15
- So the ouput will be:
- 8 4 9 10 12 5 6 11 13 14 7 15
- void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
- {
- if(node == NULL)
- return;
- if(level == 1){
- if(lev[hd-min] == 0 || lev[hd-min] == l){
- lev[hd-min] = l;
- visited[hd-min].push_back(node->data);
- }
- }
- else if(level > 1)
- {
- printBottom(node->left, level-1, hd-1, min, visited, lev, l);
- printBottom(node->right, level-1, hd+1, min, visited, lev, l);
- }
- }
- int main()
- {
- find the minimum and maximum values for hd via DFS
- 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
- map < int, vector<int> > visited; //the nodes in the bottom view
- int h = height(root);
- for (int i=h; i>0; i--){
- printBottom(root, i, 0, min, visited, lev, i);
- }
- output visited
- }
- void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
- {
- if(node == NULL)
- return;
- if(lev[hd-min] < level){
- lev[hd-min] = level;
- visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
- }
- if(lev[hd-min] <= level){
- visited[hd-min].push_back(node->data);
- }
- printBottom(node->left, level+1, hd-1, min, visited, lev);
- printBottom(node->right, level+1, hd+1, min, visited, lev);
- }
- void fillLev(Node *node, int level, int hd, int min, int lev[])
- {
- if(node == NULL)
- return;
- if(lev[hd-min] < level){
- lev[hd-min] = level;
- }
- fillLev(node->left, level+1, hd-1, min, lev);
- fillLev(node->right, level+1, hd+1, min, lev);
- }
- void printBottom(Node *node, int level, int hd, int min, int lev[])
- {
- if(node == NULL)
- return;
- if(lev[hd-min] == level){
- cout << node->data;
- }
- printBottom(node->left, level+1, hd-1, min, lev);
- printBottom(node->right, level+1, hd+1, min, lev);
- }
- public class node
- {
- public int data;
- public node left, right;
- public int hd;
- };
- // A utility function to create a new
- // Binary Tree node
- static node newNode(int item)
- {
- node temp = new node();
- temp.data = item;
- temp.left = null;
- temp.right = null;
- return temp;
- }
- static void rightViewOfBT(node root)
- {
- Queue<node> queue = new Queue<node>();
- SortedDictionary<int, int> treeMap = new SortedDictionary<int, int>();
- int hd = 0;
- root.hd = hd;
- queue.Enqueue(root);
- while(queue.Count > 0)
- {
- node temp = queue.Peek();
- queue.Dequeue();
- if (treeMap.ContainsKey(temp.hd))
- {
- treeMap[temp.hd] = temp.data;
- }
- else
- {
- treeMap.Add(temp.hd, temp.data);
- }
- if (temp.left != null)
- {
- temp.left.hd = temp.hd - 1;
- queue.Enqueue(temp.left);
- }
- if (temp.right != null)
- {
- temp.right.hd = temp.hd + 1;
- queue.Enqueue(temp.right);
- }
- }
- foreach (var tree in treeMap)
- Console.Write(tree.Value);
- }
- static void Main(string[] args)
- {
- node root = newNode(1);
- root.left = newNode(2);
- root.right = newNode(3);
- root.left.left = newNode(4);
- root.left.right = newNode(5);
- root.left.left.right = newNode(8);
- root.left.right.left = newNode(9);
- root.right.left = newNode(6);
- root.right.right = newNode(7);
- root.right.right.right = newNode(11);
- root.right.left.right = newNode(10);
- rightViewOfBT(root);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement