JavaScript/Trees/DepthFirstSearch.js at master · FullMetalAnna/JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

// 6
// / \
// 5 7
// / \ \
// 3 4 9
// / / \
// 2 8 10
// /
// 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
 * Author: Surendra Kumar
 * DFS Algorithm implementation in JavaScript
 * DFS Algorithm for traversing or searching graph data structures.
*/

functiontraverseDFS(root){
conststack=[root]
constres=[]

while(stack.length){
constcurr=stack.pop()
res.push(curr.key)

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

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

returnres.reverse()
}

functionsearchDFS(tree,value){
conststack=[]

stack.push(tree[0])

while(stack.length!==0){
for(leti=0;i<stack.length;i++){
constnode=stack.pop()

if(node.value===value){
returnnode
}
if(node.right){
stack.push(tree[node.right])
}
if(node.left){
stack.push(tree[node.left])
}
}
}
returnnull
}

consttree=[
{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}
]

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

traverseDFS(6)

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