{"id":1034,"date":"2025-09-01T14:13:12","date_gmt":"2025-09-01T08:43:12","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1034"},"modified":"2025-09-01T14:13:14","modified_gmt":"2025-09-01T08:43:14","slug":"boundary-traversal-of-binary-tree","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/boundary-traversal-of-binary-tree\/","title":{"rendered":"Boundary Traversal of Binary Tree \u2013 Detailed Explanation"},"content":{"rendered":"\n<p>You are given the root of a binary tree. Your task is to return the <strong>boundary traversal<\/strong> of the tree in <strong>anticlockwise order<\/strong> starting from the root.<\/p>\n\n\n\n<p>The boundary traversal should include:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Root node<\/strong> (only if it is not a leaf).<\/li>\n\n\n\n<li><strong>Left boundary<\/strong> (top to bottom, excluding leaves).<\/li>\n\n\n\n<li><strong>All leaf nodes<\/strong> (from left to right).<\/li>\n\n\n\n<li><strong>Right boundary<\/strong> (bottom to top, excluding leaves).<\/li>\n<\/ol>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/boundary-traversal-of-binary-tree\/1\" 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\">Example<\/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(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=\"Input:\n        20\n       \/  \\\n      8    22\n     \/ \\     \\\n    4  12     25\n       \/ \\\n      10 14\n\nOutput: 20 8 4 10 14 25 22\" 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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">8    22<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/ \\     \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">4  12     25<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">10 14<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">20 8 4 10 14 25 22<\/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(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=\"Input:\n        1\n         \\\n          2\n           \\\n            3\n             \\\n              4\n\nOutput: 1 4 3 2\" 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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">         <\/span><span style=\"color: #CE9178\">\\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">          <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #CE9178\">\\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #B5CEA8\">3<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">             <\/span><span style=\"color: #CE9178\">\\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">              <\/span><span style=\"color: #B5CEA8\">4<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">1 4 3 2<\/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>We can break down the traversal into <strong>three parts<\/strong>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Left boundary (excluding leaves):<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start from the root\u2019s left child.<\/li>\n\n\n\n<li>Keep moving left if possible, otherwise right.<\/li>\n\n\n\n<li>Stop at leaves.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Leaves (from left to right):<\/strong>\n<ul class=\"wp-block-list\">\n<li>Perform a DFS traversal.<\/li>\n\n\n\n<li>Add a node if it is a leaf (no children).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Right boundary (excluding leaves):<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start from the root\u2019s right child.<\/li>\n\n\n\n<li>Keep moving right if possible, otherwise left.<\/li>\n\n\n\n<li>Stop at leaves.<\/li>\n\n\n\n<li>Collect nodes and reverse them because we want bottom \u2192 top order.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>Finally, concatenate all three parts with the root.<\/p>\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=\"class Solution:\n    def is_leaf(self, node):\n        if node != None and node.left == None and node.right == None:\n            return True\n        return False\n\n    # Left boundary (excluding leaves) O(H)\n    def add_left_boundary(self, node, ans):\n        cur = node\n        while cur:\n            if not self.is_leaf(cur):\n                ans.append(cur.data)\n            if cur.left:\n                cur = cur.left\n            else:\n                cur = cur.right\n\n    # Leaves (left to right) O(N)\n    def add_leaves(self, node, ans):\n        if not node:\n            return\n        if self.is_leaf(node):\n            ans.append(node.data)\n            return\n        self.add_leaves(node.left, ans)\n        self.add_leaves(node.right, ans)\n\n    # Right boundary (excluding leaves), reversed later O(H)\n    def add_right_boundary(self, node, ans):\n        cur = node\n        stack = []\n        while cur:\n            if not self.is_leaf(cur):\n                stack.append(cur.data)\n            if cur.right:\n                cur = cur.right\n            else:\n                cur = cur.left\n        while stack:\n            ans.append(stack.pop())\n\n    def boundaryTraversal(self, root):\n        if not root:\n            return []\n\n        ans = []\n        if not self.is_leaf(root):\n            ans.append(root.data)\n\n        self.add_left_boundary(root.left, ans)\n        self.add_leaves(root, ans)\n        self.add_right_boundary(root.right, ans)\n\n        return ans\" 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\">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\">is_leaf<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">node<\/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 != <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> node.left == <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> node.right == <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Left boundary (excluding leaves) O(H)<\/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\">add_left_boundary<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">node<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        cur = node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> cur:<\/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\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.is_leaf(cur):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                ans.append(cur.data)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> cur.left:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                cur = cur.left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                cur = cur.right<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Leaves (left to right) O(N)<\/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\">add_leaves<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">node<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/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\"> node:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/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\">self<\/span><span style=\"color: #D4D4D4\">.is_leaf(node):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(node.data)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.add_leaves(node.left, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.add_leaves(node.right, ans)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Right boundary (excluding leaves), reversed later O(H)<\/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\">add_right_boundary<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">node<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        cur = node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        stack = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> cur:<\/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\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.is_leaf(cur):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                stack.append(cur.data)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> cur.right:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                cur = cur.right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                cur = cur.left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> stack:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(stack.pop())<\/span><\/span>\n<span class=\"line\"><\/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\">boundaryTraversal<\/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\">):<\/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\">        ans = []<\/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\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.is_leaf(root):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(root.data)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.add_left_boundary(root.left, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.add_leaves(root, ans)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.add_right_boundary(root.right, ans)<\/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\"> ans<\/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<ol class=\"wp-block-list\">\n<li><strong><code>is_leaf(node)<\/code>:<\/strong> Returns <code>True<\/code> if node has no left or right child.<\/li>\n\n\n\n<li><strong><code>add_left_boundary(node, ans)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Traverse down the left boundary.<\/li>\n\n\n\n<li>Add nodes that are not leaves.<\/li>\n\n\n\n<li>Move left if possible, otherwise right.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>add_leaves(node, ans)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Recursively traverse the whole tree.<\/li>\n\n\n\n<li>Append nodes that are leaves.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>add_right_boundary(node, ans)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Traverse down the right boundary and collect nodes (excluding leaves) in a stack.<\/li>\n\n\n\n<li>Pop from stack to add nodes in reverse order.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong><code>boundaryTraversal(root)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Add the root (if it is not a leaf).<\/li>\n\n\n\n<li>Collect left boundary.<\/li>\n\n\n\n<li>Collect leaves.<\/li>\n\n\n\n<li>Collect right boundary.<\/li>\n\n\n\n<li>Return the combined result.<\/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\">Dry Run Example<\/h2>\n\n\n\n<p>For the first tree:<\/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=\"        20\n       \/  \\\n      8    22\n     \/ \\     \\\n    4  12     25\n       \/ \\\n      10 14\" 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\">20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">8    22<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     <\/span><span style=\"color: #CE9178\">\/ \\     \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #CE9178\">4  12     25<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">10 14<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Root: <code>20<\/code><\/li>\n\n\n\n<li>Left boundary: <code>8 \u2192 4<\/code><\/li>\n\n\n\n<li>Leaves: <code>4, 10, 14, 25<\/code><\/li>\n\n\n\n<li>Right boundary: <code>22<\/code><\/li>\n<\/ul>\n\n\n\n<p>Final result: <code>[20, 8, 4, 10, 14, 25, 22]<\/code><\/p>\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>Left boundary: <code>O(H)<\/code> where <code>H<\/code> is tree height<\/li>\n\n\n\n<li>Right boundary: <code>O(H)<\/code><\/li>\n\n\n\n<li>Leaves: <code>O(N)<\/code><br>Overall: <strong>O(N)<\/strong> where <code>N<\/code> = number of nodes.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Extra stack for right boundary: <code>O(H)<\/code><\/li>\n\n\n\n<li>Recursion stack for DFS leaves: <code>O(H)<\/code><br>Worst case: <strong>O(N)<\/strong> for skewed trees.<\/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>Boundary Traversal of Binary Tree<\/strong> is done in four systematic steps:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Add root (if not leaf).<\/li>\n\n\n\n<li>Add left boundary.<\/li>\n\n\n\n<li>Add all leaves (DFS).<\/li>\n\n\n\n<li>Add right boundary in reverse.<\/li>\n<\/ol>\n\n\n\n<p>This ensures the traversal is <strong>anticlockwise<\/strong> and avoids duplication of leaf nodes.<\/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","protected":false},"excerpt":{"rendered":"<p>You are given the root of a binary tree. Your task is to return the boundary traversal of the tree in anticlockwise order starting from the root. The boundary traversal should include: Here&#8217;s the [Problem Link] to begin with. Example Example 1 Example 2 Intuition and Approach We can break down the traversal into three<\/p>\n","protected":false},"author":1,"featured_media":1035,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[14,19],"class_list":{"0":"post-1034","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-binary-trees","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/09\/tree-boundary-traversal-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\/1034","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=1034"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1034\/revisions"}],"predecessor-version":[{"id":1036,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1034\/revisions\/1036"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1035"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1034"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1034"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1034"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}