Last active
March 13, 2020 05:56
-
-
Save Prottoy2938/19a81aadc3f9a9a104421c7f1727f87c to your computer and use it in GitHub Desktop.
Depth First Search Implementation in JavaScript. Works in Binary Tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //The algorithm starts at the root node and explores as far as possible along each branch before backtracking | |
| //To simplify, In Depth First Search in Binary Search Tree, travels through one side until it reaches its end and then tries the other side. | |
| //============================================================================================================ | |
| //DFS_PreOrder | |
| //This method, visits the one specific side(either left or right) at once, and after the whole side is finished, then visits the other side. | |
| // as it goes through the tree, it pushes visited node continuously. | |
| //Example: 10 | |
| // 6 15 | |
| // 3 8 20 | |
| //result node would be =[10, 6, 3, 8, 15, 20] | |
| const DFS_PreOrder = tree => { | |
| let data = []; | |
| function traverse(node) { | |
| data.push(node.value); | |
| if (node.left) traverse(node.left); | |
| if (node.right) traverse(node.right); | |
| } | |
| traverse(tree.root); | |
| return data; | |
| }; | |
| const totalNodeDFS_PreOrder = DFS_PreOrder(BST_ROOT); | |
| //============================================================================================================ | |
| //DFS_PostOrder | |
| //this method is similar to DFS_PreOrder. Only difference is that, the DFS_PreOrder pushes node as it goes through, | |
| //but DFS_PostOrder pushes node once it reaches the end and moves backwards from there as it pushes. | |
| //Example: 10 | |
| // 6 15 | |
| // 3 8 20 | |
| //result node would be =[3, 8, 6, 20, 15, 10] | |
| const DFS_PostOrder = tree => { | |
| let data = []; | |
| function traverse(node) { | |
| data.push(node.value); | |
| if (node.left) traverse(node.left); | |
| if (node.right) traverse(node.right); | |
| } | |
| traverse(tree.root); | |
| return data; | |
| }; | |
| const totalNodeDFS_Postorder = DFS_PostOrder(BST_ROOT); | |
| //============================================================================================================ | |
| //DFS_InOrder | |
| //this method is similar to DFS_PreOrder. Main difference is that, once it finishes visiting/pushing one side, it visits the parent node and pushes it, | |
| //and after that it goes to the other side. It happens recursively. | |
| //One important thing, It returns sorted data from smaller to larger. | |
| //Example: 10 | |
| // 6 15 | |
| // 3 8 20 | |
| //result node would be =[3, 6, 8, 10, 15, 20] | |
| const DFS_INOrder = tree => { | |
| let data = []; | |
| function traverse(node) { | |
| if (node.left) traverse(node.left); | |
| data.push(node.value); | |
| if (node.right) traverse(node.right); | |
| } | |
| traverse(tree.root); | |
| return data; | |
| }; | |
| const totalNodeDFS_INOrder = DFS_INOrder(BST_ROOT); | |
| export default totalNodeDFS_INOrder; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment