{"id":89,"date":"2025-05-12T18:04:46","date_gmt":"2025-05-12T12:34:46","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=89"},"modified":"2025-05-12T18:19:09","modified_gmt":"2025-05-12T12:49:09","slug":"depth-first-search-in-binary-trees","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/","title":{"rendered":"A Beginner\u2019s Guide to Preorder, Inorder &amp; Postorder Traversals"},"content":{"rendered":"\n<p>Dive into <strong>Depth-First Search (DFS) <\/strong>on binary trees! In this friendly guide, we\u2019ll learn about preorder, inorder, and postorder traversals using simple Python recursion, perfect for LeetCode prep and coding interviews.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-49dde012-ede1-4a3a-b543-102fc297e39e\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Content:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#0-why-tree-traversals-matter\" style=\"\">Why Tree Traversals Matter<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#1-quick-visual-the-binary-tree-we%E2%80%99ll-use\" style=\"\">Quick Visual: The Binary Tree We\u2019ll Use<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#2-1-preorder-traversal-root-%E2%86%92-left-%E2%86%92-right\" style=\"\">1. Preorder Traversal (Root \u2192 Left \u2192 Right)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#3-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\" style=\"\">Intuition &amp; \u201cWhy\u201d<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#4-recursive-code-python-\" style=\"\">Recursive Code (Python)<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#5-2-inorder-traversal-left-%E2%86%92-root-%E2%86%92-right\" style=\"\">2. Inorder Traversal (Left \u2192 Root \u2192 Right)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#6-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\" style=\"\">Intuition &amp; \u201cWhy\u201d<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#7-recursive-code-python-\" style=\"\">Recursive Code (Python)<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#8-3-postorder-traversal-left-%E2%86%92-right-%E2%86%92-root\" style=\"\">3. Postorder Traversal (Left \u2192 Right \u2192 Root)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#9-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\" style=\"\">Intuition &amp; \u201cWhy\u201d<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#10-recursive-code-python-\" style=\"\">Recursive Code (Python)<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#11-putting-it-all-together\" style=\"\">Putting It All Together<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/depth-first-search-in-binary-trees\/#12-why-recursion-rocks-for-dfs\" style=\"\">Why Recursion Rocks for DFS<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-why-tree-traversals-matter\">Why Tree Traversals Matter<\/h2>\n\n\n\n<p>Imagine you\u2019re exploring a hidden maze. At each junction, you choose a path, dive deep until you hit a dead end, then backtrack. That\u2019s essentially <strong>Depth-First Search (DFS)<\/strong> in action. When our \u201cmaze\u201d is a <strong>binary tree<\/strong>, DFS gives us three classic ways to visit every node:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Preorder<\/strong>: Visit the root <em>before<\/em> its subtrees.<\/li>\n\n\n\n<li><strong>Inorder<\/strong>: Visit the root <em>between<\/em> its left and right subtrees.<\/li>\n\n\n\n<li><strong>Postorder<\/strong>: Visit the root <em>after<\/em> its subtrees.<\/li>\n<\/ol>\n\n\n\n<p>These traversal patterns aren\u2019t just academic, they\u2019re the backbone of many LeetCode challenges (think \u201cValidate BST\u201d or \u201cSerialize\/Deserialize Tree\u201d) and are super common in whiteboard interviews.<\/p>\n\n\n\n<p>Let\u2019s check each one, build up the intuition, and then translate it into clean, recursive Python code.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><em>Also read about the Python Program to <strong><a href=\"https:\/\/codeanddebug.in\/blog\/breadth-first-search-in-binary-trees\/\" 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;\">Level Order Traversals in Binary Trees<\/span><\/mark><\/a><\/strong><\/em>.<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-quick-visual-the-binary-tree-we%E2%80%99ll-use\">Quick Visual: The Binary Tree We\u2019ll Use<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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=\"      1\n     \/ \\\n    2   3\n   \/ \\   \\\n  4   5   6\" 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\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">     \/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">3<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">   \/ \\   \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">5<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">6<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Preorder<\/strong>: visit <strong>1<\/strong>, then traverse left, then right \u2192 <code>[1, 2, 4, 5, 3, 6]<\/code><\/li>\n\n\n\n<li><strong>Inorder<\/strong>: traverse left, visit <strong>1<\/strong>, then right \u2192 <code>[4, 2, 5, 1, 3, 6]<\/code><\/li>\n\n\n\n<li><strong>Postorder<\/strong>: traverse left, then right, visit <strong>1<\/strong> \u2192 <code>[4, 5, 2, 6, 3, 1]<\/code><\/li>\n<\/ul>\n\n\n\n<p>Keep these sequences in mind as we code!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-1-preorder-traversal-root-%E2%86%92-left-%E2%86%92-right\">1. Preorder Traversal (Root \u2192 Left \u2192 Right)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\"><strong>Intuition &amp; \u201cWhy\u201d<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You\u2019re a scout: you <strong>capture<\/strong> the root first (mark it visited), then <strong>explore<\/strong> deeper on the left branch, then on the right.<\/li>\n\n\n\n<li>Great for <strong>copying<\/strong> a tree (clone its structure).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-recursive-code-python-\"><strong>Recursive Code (Python)<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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=\"def preorder(root, result):\n    if not root:\n        return\n    # Visit the root\n    result.append(root.val)\n    # Explore left\n    preorder(root.left, result)\n    # Explore right\n    preorder(root.right, result)\n\nres = []\npreorder(root, res)\nprint(res)  # [1, 2, 4, 5, 3, 6]\" 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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">preorder<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Visit the root<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result.append(root.val)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    preorder(root.left, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    preorder(root.right, result)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">res = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">preorder(root, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(res)  <\/span><span style=\"color: #6A9955\"># [1, 2, 4, 5, 3, 6]<\/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\" id=\"5-2-inorder-traversal-left-%E2%86%92-root-%E2%86%92-right\">2. Inorder Traversal (Left \u2192 Root \u2192 Right)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\"><strong>Intuition &amp; \u201cWhy\u201d<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You\u2019re reading a book: you <strong>finish the left chapter<\/strong>, then <strong>read the root<\/strong>, then <strong>tackle the right chapter<\/strong>.<\/li>\n\n\n\n<li>In a <strong>binary search tree (BST)<\/strong>, inorder traversal gives you <strong>sorted order<\/strong>, super useful for checking if a tree is a valid BST.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-recursive-code-python-\"><strong>Recursive Code (Python)<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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=\"def inorder(root, result):\n    if not root:\n        return\n    # Explore left\n    inorder(root.left, result)\n    # Visit the root\n    result.append(root.val)\n    # Explore right\n    inorder(root.right, result)\n\nres = []\ninorder(root, res)\nprint(res)  # [4, 2, 5, 1, 3, 6]\" 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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">inorder<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    inorder(root.left, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Visit the root<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result.append(root.val)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    inorder(root.right, result)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">res = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">inorder(root, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(res)  <\/span><span style=\"color: #6A9955\"># [4, 2, 5, 1, 3, 6]<\/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\" id=\"8-3-postorder-traversal-left-%E2%86%92-right-%E2%86%92-root\">3. Postorder Traversal (Left \u2192 Right \u2192 Root)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition-amp-%E2%80%9Cwhy%E2%80%9D-\"><strong>Intuition &amp; \u201cWhy\u201d<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You\u2019re cleaning the mansion: <strong>clean left wing<\/strong>, <strong>clean right wing<\/strong>, and <strong>finally lock up the main door (root)<\/strong>.<\/li>\n\n\n\n<li>Perfect for <strong>deleting<\/strong> or <strong>freeing<\/strong> nodes: you want to handle children before the parent.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-recursive-code-python-\"><strong>Recursive Code (Python)<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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=\"def postorder(root, result):\n    if not root:\n        return\n    # Explore left\n    postorder(root.left, result)\n    # Explore right\n    postorder(root.right, result)\n    # Visit the root\n    result.append(root.val)\n\nres = []\npostorder(root, res)\nprint(res)  # [4, 5, 2, 6, 3, 1]\" 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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">postorder<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/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>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore left<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    postorder(root.left, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Explore right<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    postorder(root.right, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Visit the root<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result.append(root.val)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">res = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">postorder(root, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(res)  <\/span><span style=\"color: #6A9955\"># [4, 5, 2, 6, 3, 1]<\/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\" id=\"11-putting-it-all-together\">Putting It All Together<\/h2>\n\n\n\n<p>Here\u2019s a <strong>single class<\/strong> encapsulating all three traversals neatly:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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 DFSBinaryTree:\n    def preorder(self, root, res):\n        if not root: return\n        res.append(root.val)\n        self.preorder(root.left, res)\n        self.preorder(root.right, res)\n\n    def inorder(self, root, res):\n        if not root: return\n        self.inorder(root.left, res)\n        res.append(root.val)\n        self.inorder(root.right, res)\n\n    def postorder(self, root, res):\n        if not root: return\n        self.postorder(root.left, res)\n        self.postorder(root.right, res)\n        res.append(root.val)\" 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\">DFSBinaryTree<\/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\">preorder<\/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 style=\"color: #9CDCFE\">res<\/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 style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        res.append(root.val)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.preorder(root.left, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.preorder(root.right, res)<\/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\">inorder<\/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 style=\"color: #9CDCFE\">res<\/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 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\">.inorder(root.left, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        res.append(root.val)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.inorder(root.right, res)<\/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\">postorder<\/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 style=\"color: #9CDCFE\">res<\/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 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\">.postorder(root.left, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.postorder(root.right, res)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        res.append(root.val)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" 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;line-height:1.25rem;--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=\"traversals = DFSBinaryTree()\npre, ino, post = [], [], []\ntraversals.preorder(root, pre)\ntraversals.inorder(root, ino)\ntraversals.postorder(root, post)\n\nprint(&quot;Preorder =&quot;, pre)    # [1, 2, 4, 5, 3, 6]\nprint(&quot;Inorder =&quot;, ino)    # [4, 2, 5, 1, 3, 6]\nprint(&quot;Postorder =&quot;, post)   # [4, 5, 2, 6, 3, 1]\" 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\">traversals = DFSBinaryTree()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">pre, ino, post = [], [], []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">traversals.preorder(root, pre)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">traversals.inorder(root, ino)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">traversals.postorder(root, post)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;Preorder =&quot;<\/span><span style=\"color: #D4D4D4\">, pre)    <\/span><span style=\"color: #6A9955\"># [1, 2, 4, 5, 3, 6]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;Inorder =&quot;<\/span><span style=\"color: #D4D4D4\">, ino)    <\/span><span style=\"color: #6A9955\"># [4, 2, 5, 1, 3, 6]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">print<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;Postorder =&quot;<\/span><span style=\"color: #D4D4D4\">, post)   <\/span><span style=\"color: #6A9955\"># [4, 5, 2, 6, 3, 1]<\/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\" id=\"12-why-recursion-rocks-for-dfs\">Why Recursion Rocks for DFS<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Elegance<\/strong>: The call stack <strong>naturally tracks<\/strong> which node you came from, no need for manual stacks or markers.<\/li>\n\n\n\n<li><strong>Clarity<\/strong>: Each function call focuses on one node, delegating subtrees to deeper calls.<\/li>\n\n\n\n<li><strong>Conciseness<\/strong>: A few lines of code handle the entire traversal.<\/li>\n<\/ul>\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\">Master DSA with our course<\/a><\/div>\n<\/div>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><em>For any changes to the document, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n<\/blockquote>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dive into Depth-First Search (DFS) on binary trees! In this friendly guide, we\u2019ll learn about preorder, inorder, and postorder traversals using simple Python recursion, perfect for LeetCode prep and coding interviews. Why Tree Traversals Matter Imagine you\u2019re exploring a hidden maze. At each junction, you choose a path, dive deep until you hit a dead<\/p>\n","protected":false},"author":1,"featured_media":91,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[14],"class_list":{"0":"post-89","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"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/05\/depth-first-search-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\/89","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=89"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/89\/revisions"}],"predecessor-version":[{"id":100,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/89\/revisions\/100"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/91"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=89"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=89"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=89"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}