{"id":1083,"date":"2025-09-02T12:08:33","date_gmt":"2025-09-02T06:38:33","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1083"},"modified":"2025-09-02T12:08:34","modified_gmt":"2025-09-02T06:38:34","slug":"vertical-order-traversal-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/vertical-order-traversal-of-a-binary-tree\/","title":{"rendered":"Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution"},"content":{"rendered":"\n<p>The <strong>Vertical Order Traversal of a Binary Tree<\/strong> problem asks us to traverse a binary tree in a special way:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Nodes are grouped by their <strong>column index<\/strong> (x-coordinate).<\/li>\n\n\n\n<li>Within the same column, nodes are ordered by <strong>row index<\/strong> (y-coordinate).<\/li>\n\n\n\n<li>If multiple nodes share the same (x, y), sort them by their values.<\/li>\n<\/ul>\n\n\n\n<p>We must return a list of lists, where each inner list represents a vertical column of the tree.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/vertical-order-traversal-of-a-binary-tree\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Examples<\/h3>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: root = [3,9,20,null,null,15,7]\nOutput: [[9],[3,15],[20],[7]]\nExplanation:\n- Column -1 \u2192 [9]\n- Column 0  \u2192 [3,15]\n- Column 1  \u2192 [20]\n- Column 2  \u2192 [7]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">root = [3,9,20,null,null,15,7]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: [[<\/span><span style=\"color: #B5CEA8\">9<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">15<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">20<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">7<\/span><span style=\"color: #D4D4D4\">]]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Explanation<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">- <\/span><span style=\"color: #CE9178\">Column -1 \u2192 [9]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">- <\/span><span style=\"color: #CE9178\">Column 0  \u2192 [3,15]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">- <\/span><span style=\"color: #CE9178\">Column 1  \u2192 [20]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">- <\/span><span style=\"color: #CE9178\">Column 2  \u2192 [7]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: root = [1,2,3,4,5,6,7]\nOutput: [[4],[2],[1,5,6],[3],[7]]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">root = [1,2,3,4,5,6,7]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: [[<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">5<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">6<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">],[<\/span><span style=\"color: #B5CEA8\">7<\/span><span style=\"color: #D4D4D4\">]]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition and Approach<\/h2>\n\n\n\n<p>To solve this problem, we map each node to a coordinate system:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The <strong>root node<\/strong> starts at position <code>(x=0, y=0)<\/code>.<\/li>\n\n\n\n<li>For <strong>left child<\/strong>, move to <code>(x-1, y+1)<\/code>.<\/li>\n\n\n\n<li>For <strong>right child<\/strong>, move to <code>(x+1, y+1)<\/code>.<\/li>\n<\/ul>\n\n\n\n<p>This way:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>x<\/code> defines the <strong>vertical column index<\/strong>.<\/li>\n\n\n\n<li><code>y<\/code> defines the <strong>row level<\/strong>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-step approach:<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>BFS Traversal:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Use a queue to traverse level by level.<\/li>\n\n\n\n<li>For each node, store its <code>(x, y)<\/code> coordinates.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Group Nodes by Coordinates:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Use a dictionary <code>nodes_map[x][y]<\/code> to store all nodes that appear at <code>(x, y)<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Sorting:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Sort by <code>x<\/code> (columns left to right).<\/li>\n\n\n\n<li>For each column, sort by <code>y<\/code> (top to bottom).<\/li>\n\n\n\n<li>If multiple nodes share the same <code>(x, y)<\/code>, sort them by node value.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Build Result:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Combine values in order to create the vertical traversal list.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Implementation<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"from collections import deque\nfrom typing import Optional, List\n\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n    def verticalTraversal(self, root: Optional['TreeNode']) -&gt; List[List[int]]:\n        if not root:\n            return []\n\n        # nodes_map[x][y] -&gt; list of node values at coordinate (x, y)\n        nodes_map = {}  # dict[int, dict[int, list[int]]]\n\n        # BFS: store (node, x, y)\n        q = deque([(root, 0, 0)])\n\n        while q:\n            node, x, y = q.popleft()\n\n            # Ensure x key exists\n            if x not in nodes_map:\n                nodes_map[x] = {}\n            # Ensure y key exists for this x\n            if y not in nodes_map[x]:\n                nodes_map[x][y] = []\n            nodes_map[x][y].append(node.val)\n\n            if node.left:\n                q.append((node.left, x - 1, y + 1))\n            if node.right:\n                q.append((node.right, x + 1, y + 1))\n\n        # Build result: sort columns by x, rows by y, and values within same (x,y)\n        result = []\n        for x in sorted(nodes_map.keys()):\n            column = []\n            for y in sorted(nodes_map[x].keys()):\n                column.extend(sorted(nodes_map[x][y]))\n            result.append(column)\n\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> collections <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> deque<\/span><\/span>\n<span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> typing <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> Optional, List<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\"># Definition for a binary tree node.<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\"># class TreeNode:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#     def __init__(self, val=0, left=None, right=None):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.val = val<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.left = left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #6A9955\">#         self.right = right<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">verticalTraversal<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">: Optional[<\/span><span style=\"color: #CE9178\">&#39;TreeNode&#39;<\/span><span style=\"color: #D4D4D4\">]) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> root:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> []<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># nodes_map[x][y] -&gt; list of node values at coordinate (x, y)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        nodes_map = {}  <\/span><span style=\"color: #6A9955\"># dict[int, dict[int, list[int]]]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># BFS: store (node, x, y)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        q = deque([(root, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">)])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> q:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            node, x, y = q.popleft()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Ensure x key exists<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> x <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> nodes_map:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                nodes_map[x] = {}<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Ensure y key exists for this x<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> y <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> nodes_map[x]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                nodes_map[x][y] = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            nodes_map[x][y].append(node.val)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> node.left:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                q.append((node.left, x - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, y + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> node.right:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                q.append((node.right, x + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, y + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">))<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Build result: sort columns by x, rows by y, and values within same (x,y)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> x <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">sorted<\/span><span style=\"color: #D4D4D4\">(nodes_map.keys()):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            column = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> y <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">sorted<\/span><span style=\"color: #D4D4D4\">(nodes_map[x].keys()):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                column.extend(<\/span><span style=\"color: #DCDCAA\">sorted<\/span><span style=\"color: #D4D4D4\">(nodes_map[x][y]))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            result.append(column)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Explanation<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>nodes_map<\/code>: Nested dictionary to group nodes by <code>(x, y)<\/code>.<\/li>\n\n\n\n<li>BFS ensures we visit nodes level by level.<\/li>\n\n\n\n<li>Left child goes to <code>(x-1, y+1)<\/code>, right child to <code>(x+1, y+1)<\/code>.<\/li>\n\n\n\n<li>Sorting ensures correct ordering of columns, rows, and values.<\/li>\n\n\n\n<li>Finally, we merge values into lists for each vertical column.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Dry Run<\/h2>\n\n\n\n<p>Input: <code>root = [3,9,20,null,null,15,7]<\/code><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start <code>(3, x=0, y=0)<\/code> \u2192 store at nodes_map[0][0] = [3].<\/li>\n\n\n\n<li>Left <code>(9, x=-1, y=1)<\/code> \u2192 nodes_map[-1][1] = [9].<\/li>\n\n\n\n<li>Right <code>(20, x=1, y=1)<\/code> \u2192 nodes_map[1][1] = [20].<\/li>\n\n\n\n<li>Left of 20 <code>(15, x=0, y=2)<\/code> \u2192 nodes_map[0][2] = [15].<\/li>\n\n\n\n<li>Right of 20 <code>(7, x=2, y=2)<\/code> \u2192 nodes_map[2][2] = [7].<\/li>\n<\/ol>\n\n\n\n<p>Final sorted traversal:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"[ [9], [3,15], [20], [7] ]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">[ [<\/span><span style=\"color: #B5CEA8\">9<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">15<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">20<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">7<\/span><span style=\"color: #D4D4D4\">] ]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Time and Space Complexity<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>BFS traversal: O(N)<\/li>\n\n\n\n<li>Sorting: O(N log N) (columns + rows + values)<\/li>\n\n\n\n<li>Total: <strong>O(N log N)<\/strong><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Storing all nodes in <code>nodes_map<\/code>: O(N)<\/li>\n\n\n\n<li>Queue for BFS: O(N)<\/li>\n\n\n\n<li>Total: <strong>O(N)<\/strong><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The <strong>Vertical Order Traversal of a Binary Tree<\/strong> problem can be solved efficiently using BFS with coordinate mapping.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Assign coordinates <code>(x, y)<\/code> to nodes.<\/li>\n\n\n\n<li>Use a nested dictionary to group nodes.<\/li>\n\n\n\n<li>Sort by column, row, and value to ensure correct ordering.<\/li>\n<\/ul>\n\n\n\n<p>This approach ensures correctness and efficiency, running in <strong>O(N log N)<\/strong> time with <strong>O(N)<\/strong> space.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Vertical Order Traversal of a Binary Tree problem asks us to traverse a binary tree in a special way: We must return a list of lists, where each inner list represents a vertical column of the tree. Here&#8217;s the [Problem Link] to begin with. Examples Example 1 Example 2 Intuition and Approach To solve<\/p>\n","protected":false},"author":1,"featured_media":1085,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[14,18],"class_list":{"0":"post-1083","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-binary-trees","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/09\/vertical-order-traversal-of-a-binary-tree-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1083","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1083"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1083\/revisions"}],"predecessor-version":[{"id":1086,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1083\/revisions\/1086"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1085"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1083"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1083"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}