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. OK, I Understand
 
Top