Skip to content

fixes: #1280 and test: added tests for DFS algorithm #1303

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Mar 1, 2023
Merged

fixes: #1280 and test: added tests for DFS algorithm #1303

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
0015de6
fix: fixed error in DepthFirstSearch algorithm and test: added tests …
Ranganathan7 Feb 27, 2023
7cd3870
changed traverseDFS function parameters in DepthFirstSearch.js file
Ranganathan7 Feb 28, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
35 changes: 16 additions & 19 deletions Trees/DepthFirstSearch.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,35 +4,32 @@
* DFS Algorithm for traversing or searching graph data structures.
*/

function traverseDFS (root) {
const stack = [root]
// traverses a give tree from specified root's value
function traverseDFS (tree, rootValue) {
const stack = []
const res = []

stack.push(searchDFS(tree, rootValue))
// if root is not present in the tree, returning empty array
if (!stack[0]) return res
while (stack.length) {
const curr = stack.pop()
res.push(curr.key)

if (curr.right) {
stack.push(curr.right)
}

res.push(curr.value)
if (curr.left) {
stack.push(curr.left)
stack.push(tree[curr.left])
}
if (curr.right) {
stack.push(tree[curr.right])
}
}

return res.reverse()
}

function searchDFS (tree, value) {
const stack = []

stack.push(tree[0])

while (stack.length !== 0) {
for (let i = 0; i < stack.length; i++) {
const node = stack.pop()

if (node.value === value) {
return node
}
Expand All @@ -59,11 +56,10 @@ const tree = [
{ value: 10, left: null, right: null },
{ value: 1, left: null, right: null }
]

searchDFS(tree, 9)
searchDFS(tree, 10)

traverseDFS(6)
searchDFS(tree, 9) // { value: 9, left: 7, right: 8 }
searchDFS(tree, 200) // null
traverseDFS(tree, 6) // [ 1, 2, 3, 4, 5, 8, 10, 9, 7, 6 ]
traverseDFS(tree, 200) // []

// 6
// / \
Expand All @@ -74,3 +70,4 @@ traverseDFS(6)
// 2 8 10
// /
// 1
export { searchDFS, traverseDFS }
46 changes: 46 additions & 0 deletions Trees/test/DepthFirstSearch.test.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,46 @@
import { searchDFS, traverseDFS } from '../DepthFirstSearch'

describe('Depth First Tree Traversal', () => {
const tree = [
{ value: 6, left: 1, right: 2 },
{ value: 5, left: 3, right: 4 },
{ value: 7, left: null, right: 5 },
{ value: 3, left: 6, right: null },
{ value: 4, left: null, right: null },
{ value: 9, left: 7, right: 8 },
{ value: 2, left: 9, right: null },
{ value: 8, left: null, right: null },
{ value: 10, left: null, right: null },
{ value: 1, left: null, right: null }
]

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1

it('should be null if given value is not present in the tree - DF Search', () => {
const res = searchDFS(tree, 200)
expect(res).toStrictEqual(null)
})

it('should return the node if given value is present in the tree - DF Search', () => {
const res = searchDFS(tree, 9)
expect(res).toStrictEqual({ value: 9, left: 7, right: 8 })
})

it('should return empty array if given root is not present in the tree - DF Traversal', () => {
const traversal = traverseDFS(tree, 200)
expect(traversal).toStrictEqual([])
})

it('should return DFT array of given tree from specified root if given root is present in the tree - DF Traversal', () => {
const traversal = traverseDFS(tree, 6)
expect(traversal).toStrictEqual([1, 2, 3, 4, 5, 8, 10, 9, 7, 6])
})
})