DFS -> InOrder using recursion

nishantml · nishantml · commit 88b6504bab45 · 2020-03-27T19:27:54.000+05:30
diff --git a/.ipynb_checkpoints/Searching-checkpoint.ipynb b/.ipynb_checkpoints/Searching-checkpoint.ipynb
@@ -8,6 +8,9 @@
     "1. Linear Search \n",
     "2. Binary Search \n",
     "3. Depth First Search\n",
+    "   - inOrder\n",
+    "   - preOrder\n",
+    "   - postOrder\n",
     "4. Breadth First Search"
    ]
   },
@@ -124,7 +127,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 102,
+   "execution_count": 41,
    "metadata": {},
    "outputs": [
     {
@@ -134,7 +137,9 @@
       "Breadth First Search\n",
       "[9, 4, 20, 1, 6, 15, 170]\n",
       "Breadth First Search using Recursion\n",
-      "[9, 4, 20, 1, 6, 15, 170]\n"
+      "[9, 4, 20, 1, 6, 15, 170]\n",
+      "DFS Inorder uisng recursion -> LPR\n",
+      "[1, 4, 6, 9, 15, 20, 170]\n"
      ]
     }
    ],
@@ -207,9 +212,29 @@
     "            queue.append(currentNode.right)\n",
     "        \n",
     "        return self.breadthFirstSearchRecursive(queue,bfsList)\n",
+    "    \n",
+    "    def DFSOLDWAYInorder(self,root): \n",
+    "        \"\"\"DFS -> 1. inoder traversal of the BST \"\"\"\n",
+    "        currentNode = root\n",
+    "        if root: \n",
+    "            self.DFSInorder(root.left) \n",
+    "            print(root.val) \n",
+    "            self.DFSInorder(root.right)\n",
+    "    def DFSInorder(self):\n",
+    "        \"\"\"DFS Inorder uisng recursion -> LPR\"\"\"\n",
+    "        return traverseInOrder(self.root,[])\n",
     "\n",
     "            \n",
-    "            \n",
+    "def traverseInOrder(node,InLst):\n",
+    "    \"\"\"LPR\"\"\"\n",
+    "#     print(node.val)\n",
+    "#     print(InLst)\n",
+    "    if node.left:\n",
+    "        traverseInOrder(node.left,InLst)\n",
+    "    InLst.append(node.val)\n",
+    "    if node.right:\n",
+    "        traverseInOrder(node.right,InLst)\n",
+    "    return InLst            \n",
     "        \n",
     "        \n",
     "bst = BST()\n",
@@ -223,7 +248,9 @@
     "print(bst.breadthFirstSearch.__doc__)\n",
     "print(bst.breadthFirstSearch())\n",
     "print(bst.breadthFirstSearchRecursive.__doc__)\n",
-    "print(bst.breadthFirstSearchRecursive([bst.root],[]))"
+    "print(bst.breadthFirstSearchRecursive([bst.root],[]))\n",
+    "print(bst.DFSInorder.__doc__)\n",
+    "print(bst.DFSInorder())"
    ]
   },
   {
diff --git a/Searching.ipynb b/Searching.ipynb
@@ -8,6 +8,9 @@
     "1. Linear Search \n",
     "2. Binary Search \n",
     "3. Depth First Search\n",
+    "   - inOrder\n",
+    "   - preOrder\n",
+    "   - postOrder\n",
     "4. Breadth First Search"
    ]
   },
@@ -124,7 +127,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 102,
+   "execution_count": 41,
    "metadata": {},
    "outputs": [
     {
@@ -134,7 +137,9 @@
       "Breadth First Search\n",
       "[9, 4, 20, 1, 6, 15, 170]\n",
       "Breadth First Search using Recursion\n",
-      "[9, 4, 20, 1, 6, 15, 170]\n"
+      "[9, 4, 20, 1, 6, 15, 170]\n",
+      "DFS Inorder uisng recursion -> LPR\n",
+      "[1, 4, 6, 9, 15, 20, 170]\n"
      ]
     }
    ],
@@ -207,9 +212,29 @@
     "            queue.append(currentNode.right)\n",
     "        \n",
     "        return self.breadthFirstSearchRecursive(queue,bfsList)\n",
+    "    \n",
+    "    def DFSOLDWAYInorder(self,root): \n",
+    "        \"\"\"DFS -> 1. inoder traversal of the BST \"\"\"\n",
+    "        currentNode = root\n",
+    "        if root: \n",
+    "            self.DFSInorder(root.left) \n",
+    "            print(root.val) \n",
+    "            self.DFSInorder(root.right)\n",
+    "    def DFSInorder(self):\n",
+    "        \"\"\"DFS Inorder uisng recursion -> LPR\"\"\"\n",
+    "        return traverseInOrder(self.root,[])\n",
     "\n",
     "            \n",
-    "            \n",
+    "def traverseInOrder(node,InLst):\n",
+    "    \"\"\"LPR\"\"\"\n",
+    "#     print(node.val)\n",
+    "#     print(InLst)\n",
+    "    if node.left:\n",
+    "        traverseInOrder(node.left,InLst)\n",
+    "    InLst.append(node.val)\n",
+    "    if node.right:\n",
+    "        traverseInOrder(node.right,InLst)\n",
+    "    return InLst            \n",
     "        \n",
     "        \n",
     "bst = BST()\n",
@@ -223,7 +248,9 @@
     "print(bst.breadthFirstSearch.__doc__)\n",
     "print(bst.breadthFirstSearch())\n",
     "print(bst.breadthFirstSearchRecursive.__doc__)\n",
-    "print(bst.breadthFirstSearchRecursive([bst.root],[]))"
+    "print(bst.breadthFirstSearchRecursive([bst.root],[]))\n",
+    "print(bst.DFSInorder.__doc__)\n",
+    "print(bst.DFSInorder())"
    ]
   },
   {
