{"id":3910,"date":"2021-11-19T15:08:34","date_gmt":"2021-11-19T09:38:34","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3910"},"modified":"2021-11-19T15:08:35","modified_gmt":"2021-11-19T09:38:35","slug":"vertical-order-traversal-of-binary-tree","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/vertical-order-traversal-of-binary-tree\/","title":{"rendered":"Vertical Order Traversal Of Binary Tree"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-hashmap-based-approach\">Approach 2 (HashMap Based Approach)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python---implementation\">Python<strong> <\/strong>Implementation<\/a><\/li><\/ul><li><a href=\"#approach-3-bfs-based-approach\">Approach 3 (BFS Based Approach)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-bfs-approach\">C++ Code For BFS Approach<\/a><\/li><li><a href=\"#java-code-for-bfs-approach-\">Java Code For BFS Approach <\/a><\/li><li><a href=\"#python-code-for-bfs-approach-\">Python Code For BFS Approach <\/a><\/li><\/ul><li><a href=\"#practice-problem\">Practice Problem<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a binary tree, print it vertically.<\/p>\n\n\n\n<p><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4084 pk-lazyload\"  width=\"538\"  height=\"534\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 538px) 100vw, 538px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-1024x1017.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-1024x1017.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-300x298.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-150x150.png 150w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-768x763.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-380x377.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-550x546.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-800x795.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6-1160x1152.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image1-6.png 1211w\" ><\/figure><\/div>\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>4<br>2<br>1 5 6<br>3 8<br>7\u00a0<br>9<\/p>\n\n\n\n<p><strong>Explanation 1:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4085 pk-lazyload\"  width=\"581\"  height=\"577\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 581px) 100vw, 581px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-1024x1017.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-1024x1017.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-300x298.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-150x150.png 150w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-768x763.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-110x110.png 110w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-380x377.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-550x546.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-800x795.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3-1160x1152.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image2-3.png 1211w\" ><\/figure><\/div>\n\n\n\n<p>The diagram shows how the vertical traversal of the tree is calculated.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>The naive idea is to find the<strong> maximum and minimum horizontal distances<\/strong> with respect to the root of the graph. After we have the range [min, max], we iterate over all the <strong>lines <\/strong>from the minimum to the maximum(refer to diagram above) and print the nodes lying on those lines in order. The traversal on the tree can be done recursively as follows for the horizontal distances.<\/p>\n\n\n\n<ul><li>function(root.left, distance &#8211; 1)<\/li><li>function(root.right, distance + 1)<\/li><\/ul>\n\n\n\n<p>At each step of recursion, we take the maximum and minimum of the <strong>distance.<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\n  public:\n    void distanceRoot(TreeNode * root, int &amp;amp; low, int &amp;amp; high, int horDist) {\n      if (root == NULL) {\n        return;\n      }\n      low = min(low, horDist);\n      high = max(high, horDist);\n      distanceRoot(root -&amp;gt; left, low, high, horDist - 1);\n      distanceRoot(root -&amp;gt; right, low, high, horDist + 1);\n    }\n  void getFromLine(TreeNode * root, int num, int horDist, vector &amp;lt; int &amp;gt; &amp;amp; line) {\n    if (root == NULL) {\n      return;\n    }\n    if (horDist == num) {\n      line.push_back(root -&amp;gt; val);\n    }\n getFromLine(root -&amp;gt; left, num, horDist - 1, line);\n    getFromLine(root -&amp;gt; right, num, horDist + 1, line);\n  }\n  vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; verticalTraversal(TreeNode * root) {\n    vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; result;\n    int low = 0, high = 0;\n    distanceRoot(root, low, high, 0);\n    for (int i = low; i &amp;lt;= high; i++) {\n      vector &amp;lt; int &amp;gt; line;\n      getFromLine(root, i, 0, line);\n      result.push_back(line);\n    }\n    return result;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n *\/\nclass Solution {\n  public void distanceRoot(TreeNode root, int[] low, int[] high, int horDist) {\n    if (root == null) {\n      return;\n    }\n    low[0] = Math.min(low[0], horDist);\n    high[0] = Math.max(high[0], horDist);\n    distanceRoot(root.left, low, high, horDist - 1);\n    distanceRoot(root.right, low, high, horDist + 1);\n  }\n  public void getFromLine(TreeNode root, int num, int horDist, List &amp;lt; Integer &amp;gt; line[]) {\n    if (root == null) {\n      return;\n    }\n    if (horDist == num) {\n      line[0].add(root.val);\n    }\n    getFromLine(root.left, num, horDist - 1, line);\n    getFromLine(root.right, num, horDist + 1, line);\n  }\n  public List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; verticalTraversal(TreeNode root) {\n    List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; result = new ArrayList &amp;lt; &amp;gt; ();\n    int[] low = new int[1];\n    int[] high = new int[1];\n    distanceRoot(root, low, high, 0);\n    for (int i = low[0]; i &amp;lt;= high[0]; i++) {\n      List &amp;lt; Integer &amp;gt; line[] = new ArrayList[1];\n      line[0] = new ArrayList &amp;lt; Integer &amp;gt; ();\n      getFromLine(root, i, 0, line);\n      result.add(line[0]);\n    }\n    return result;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def distanceRoot(self, root, low, high, horDist):\n        if not root:\n            return\n        low[0] = min(low[0], horDist)\n        high[0] = max(high[0], horDist)\n        self.distanceRoot(root.left, low, high, horDist - 1)\n        self.distanceRoot(root.right, low, high, horDist + 1)\n  def getFromLine(self, root, num, horDist, line):\n        if not root:\n            return\n        if horDist == num:\n            line.append(root.val)\n        self.getFromLine(root.left, num, horDist - 1, line)\n        self.getFromLine(root.right, num, horDist + 1, line)\n\n    def verticalTraversal(self, root):\n        \"\"\"\n        :type root: TreeNode\n        :rtype: List[List[int]]\n        \"\"\"\n        low = [0]\n        high = [0]\n        result = []\n        self.distanceRoot(root, low, high, 0)\n        for i in range(low[0], high[0] + 1):\n            line = []\n            self.getFromLine(root, i, 0, line)\n            result.append(line)\n        return result<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n * n)<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2-hashmap-based-approach\">Approach 2 (HashMap Based Approach)<\/h2>\n\n\n\n<p>We can optimize the above naive approach by using a <strong>hashmap<\/strong>. Observe that all nodes which have the same horizontal distance from the root, <strong>lie on the same vertical line<\/strong>. So, by making the horizontal distances the <strong>key<\/strong> of the map, we can recursively push the nodes, into the<strong> proper key<\/strong> container while calculating the horizontal distances in the same recursive calls themselves.<\/p>\n\n\n\n<p>The algorithm is as follows:<\/p>\n\n\n\n<ul><li>Initialize a Map with <strong>[Key, Value]<\/strong> pair as <strong>[Integer, Vector&lt;Integer&gt;].<\/strong><\/li><li>Recursively traverse on the tree (both left and right child) keeping track of the <strong>horizontal distances<\/strong> with respect to the <strong>root<\/strong> node.<\/li><li>With the current <strong>horizontal distance<\/strong> as the key, push the current node, into the map of vectors.<\/li><li>Once the recursion terminates, we store each of the values(vectors) in the map, for <strong>distinct keys<\/strong>, and return them.<\/li><\/ul>\n\n\n\n<p>The thing to note about this approach is that it may not print the nodes in the same vertical order in which they appear in the tree.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\n  public:\n    void getVerticalTraversal(TreeNode * root, int horDist, map &amp;lt; int, vector &amp;lt; int &amp;gt;&amp;gt; &amp;amp; m) {\n      if (root == NULL) {\n        return;\n      }\n      m[horDist].push_back(root -&amp;gt; val);\n      getVerticalTraversal(root -&amp;gt; left, horDist - 1, m);\n      getVerticalTraversal(root -&amp;gt; right, horDist + 1, m);\n    }\n  vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; verticalTraversal(TreeNode * root) {\n    map &amp;lt; int, vector &amp;lt; int &amp;gt;&amp;gt; m;\n    getVerticalTraversal(root, 0, m);\n    vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; result;\n    for (auto x: m) {\n      result.push_back(x.second);\n   }\n    return result;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n *\/\nclass Solution {\n    public void getFromLine(TreeNode root, int num, int horDist, List &amp;lt; Integer &amp;gt; line[]) {\n    if (root == null) {\n      return;\n    }\n    if (horDist == num) {\n      line[0].add(root.val);\n    }\n    getFromLine(root.left, num, horDist - 1, line);\n    getFromLine(root.right, num, horDist + 1, line);\n  }\n  public List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; verticalTraversal(TreeNode root) {\n    List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; result = new ArrayList &amp;lt; &amp;gt; ();\n    int[] low = new int[1];\n    int[] high = new int[1];\n    distanceRoot(root, low, high, 0);\n for (int i = low[0]; i &amp;lt;= high[0]; i++) {\n      List &amp;lt; Integer &amp;gt; line[] = new ArrayList[1];\n      line[0] = new ArrayList &amp;lt; Integer &amp;gt; ();\n      getFromLine(root, i, 0, line);\n      result.add(line[0]);\n    }\n    return result;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python---implementation\"><span id=\"python-implementation\">Python<strong> <\/strong>Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def getVerticalTraversal(self, root, horDist, m):\n        if not root:\n            return\n        try:\n            m[horDist].append(root.val)\n        except:\n            m[horDist] = [root.val]\n        self.getVerticalTraversal(root.left, horDist - 1, m)\n        self.getVerticalTraversal(root.right, horDist + 1, m)\n\n    def verticalTraversal(self, root):\n        \"\"\"\n        :type root: TreeNode\n        :rtype: List[List[int]]\n        \"\"\"\n        result = []\n        m = dict()\n        self.getVerticalTraversal(root, 0, m)\n        for res in sorted(m.keys()):\n            result.append(m[res])\n        return result<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n * logn) or O(n) depending on the type of map used.<\/li><li><strong>Space Complexity:<\/strong> O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"approach-3-bfs-based-approach\">Approach 3 (BFS Based Approach)<\/h2>\n\n\n\n<p>To solve the issue of the nodes not coming in order, we can use a level order traversal-based approach on this tree. Using level order traversal ensures that a node that is below another node in the same vertical line, comes after that node when the results are being printed. The algorithm is described as follows:<\/p>\n\n\n\n<ul><li>Declare a map for branches of each node.<\/li><li>Start a <strong>BFS<\/strong> or level order traversal from each node.<\/li><li>Initialize a queue, which holds the following information, <strong>the data of the node and its horizontal distance from the root<\/strong> (can also be identified as its line number).<\/li><li>Now while the queue is not emptied, do the following,<ul><li>Take the top element from the queue, pop it, and add its data in the corresponding branch\u2019s vector.<\/li><li>If the left child of the node is not null, push it into the queue, with branch number as <strong>current branch number &#8211; 1<\/strong>.<\/li><li>If the right child of the node is not null, push it into the queue, with branch number as <strong>current branch number + 1<\/strong>.<\/li><\/ul><\/li><li>Print\/Return the values from the map accordingly in proper order.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-bfs-approach\">C++ Code For BFS Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n *\/\nclass Solution {\n  public:\n    void getTraversal(TreeNode * root, vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; &amp;amp; res) {\n      if (root == NULL) {\n        return;\n  }\n      int horDist = 0;\n      map &amp;lt; int, vector &amp;lt; int &amp;gt;&amp;gt; m;\n      queue &amp;lt; pair &amp;lt; TreeNode * , int &amp;gt;&amp;gt; q;\n      q.push({\n        root,\n        horDist\n      });\n      while (!q.empty()) {\n        auto x = q.front();\n        q.pop();\n        TreeNode * u = x.first;\n        horDist = x.second;\n        m[horDist].push_back(u -&amp;gt; val);\n        if (u -&amp;gt; left != NULL) {\n          q.push({\n            u -&amp;gt; left,\n            horDist - 1\n          });\n        }\n        if (u -&amp;gt; right != NULL) {\n          q.push({\n            u -&amp;gt; right,\n            horDist + 1\n          });\n        }\n      }\n      for (auto x: m) {\n        res.push_back(x.second);\n      }\n    }\n  vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; verticalTraversal(TreeNode * root) {\n    vector &amp;lt; vector &amp;lt; int &amp;gt;&amp;gt; result;\n    getTraversal(root, result);\n    return result;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code-for-bfs-approach-\"><span id=\"java-code-for-bfs-approach\">Java Code For BFS Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n *\/\nclass Q_pair {\n  int hor_dist;\n  TreeNode node;\n  Q_pair(int hor_dist, TreeNode node) {\n    this.hor_dist = hor_dist;\n    this.node = node;\n\n  }\n}\nclass Solution {\n  public List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; verticalTraversal(TreeNode root) {\n    List &amp;lt; List &amp;lt; Integer &amp;gt;&amp;gt; result = new ArrayList &amp;lt; &amp;gt; ();\n    if (root == null)\n      return result;\n    TreeMap &amp;lt; Integer, List &amp;lt; Integer &amp;gt; &amp;gt; map = new TreeMap &amp;lt; &amp;gt; ();\n    int hor_d = 0;\n    Queue &amp;lt; Q_pair &amp;gt; q = new LinkedList &amp;lt; &amp;gt; ();\n    q.add(new Q_pair(0, root));\n    while (!q.isEmpty()) {\n      Q_pair temp = q.poll();\n      hor_d = temp.hor_dist;\n      TreeNode node = temp.node;\n   if (map.containsKey(hor_d)) {\n        map.get(hor_d).add(node.val);\n      } else {\n        List &amp;lt; Integer &amp;gt; arr = new ArrayList &amp;lt; &amp;gt; ();\n        arr.add(node.val);\n        map.put(hor_d, arr);\n      }\n      if (node.left != null)\n        q.add(new Q_pair(hor_d - 1, node.left));\n      if (node.right != null)\n        q.add(new Q_pair(hor_d + 1, node.right));\n    }\n\n    for (Map.Entry &amp;lt; Integer, List &amp;lt; Integer &amp;gt; &amp;gt; entry: map.entrySet()) {\n      result.add(entry.getValue());\n\n    }\n    return result;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code-for-bfs-approach-\"><span id=\"python-code-for-bfs-approach\">Python Code For BFS Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def traverse(self, root, res):\n        if not root:\n            return\n        queue = []\n        m = {}\n        horDistm = {}\n        queue.append(root)\n        horDistm[root] = 0\n        m[0] = [root.val]\n        while len(queue) &amp;gt; 0:\n            u = queue.pop(0)\n            if u.left:\n                queue.append(u.left)\n                horDistm[u.left] = horDistm[u] - 1\n                horDist = horDistm[u.left]\n                if m.get(horDist) is None:\n                    m[horDist] = []\n                    m[horDist].append(u.left.val)\n                else:\n                    m[horDist].append(u.left.val)\n            if u.right:\n                queue.append(u.right)\n                horDistm[u.right] = horDistm[u] + 1\n                horDist = horDistm[u.right]\n                if m.get(horDist) is None:\n                    m[horDist] = []\n m[horDist].append(u.right.val)\n                else:\n                    m[horDist].append(u.right.val)\n        m_ = collections.OrderedDict(sorted(m.items()))\n        for i in m_.values():\n            res.append(i)\n\n    def verticalTraversal(self, root):\n        \"\"\"\n        :type root: TreeNode\n        :rtype: List[List[int]]\n        \"\"\"\n        res = []\n        self.traverse(root, res)\n        return res\n<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(n * logn) or O(n) depending on the type of map used.<\/li><li><strong>Space Complexity:<\/strong> O(n)<\/li><\/ul>\n\n\n\n<h2 id=\"practice-problem\">Practice Problem<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/old\/problems\/vertical-order-traversal-of-binary-tree\/\" target=\"_blank\">Vertical Order Traversal<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. How does the type of map determine the time complexity of the programs?<\/strong><br>A. Different maps are implemented internally in different manners. Some are implemented using <strong>hashing<\/strong>, taking up <strong>constant lookup times<\/strong>, while others are implemented using <strong>AVL or Red-Black Trees<\/strong> which take up a <strong>logarithmic factor<\/strong> for lookups and updates.<\/p>\n\n\n\n<p><strong>Q. What are the different ways of traversing a binary tree?<\/strong><br>A. There are different ways of traversing a binary tree such as <strong>Preorder Traversal, Postorder Traversal, Level Order Traversal<\/strong>, etc.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a binary tree, print it vertically. Sample Test Cases Input 1: Output 1: 421 5&hellip;\n","protected":false},"author":5,"featured_media":4095,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[585],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3910"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3910"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3910\/revisions"}],"predecessor-version":[{"id":4096,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3910\/revisions\/4096"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4095"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}