Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1d252d7

Browse files
authored
feat: add tests for binary search trees (#1769)
1 parenta62a46e commit1d252d7

File tree

2 files changed

+76
-7
lines changed

2 files changed

+76
-7
lines changed

‎Data-Structures/Tree/BinarySearchTree.js

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -36,13 +36,13 @@ const Node = (function Node() {
3636
visit(output=(value)=>console.log(value)){
3737
// Recursively go left
3838
if(this.left!==null){
39-
this.left.visit()
39+
this.left.visit(output)
4040
}
4141
// Print out value
4242
output(this.value)
4343
// Recursively go right
4444
if(this.right!==null){
45-
this.right.visit()
45+
this.right.visit(output)
4646
}
4747
}
4848

@@ -116,20 +116,23 @@ const Tree = (function () {
116116
}
117117

118118
// Inorder traversal
119-
traverse(){
119+
traverse(output=(value)=>console.log(value)){
120120
if(!this.root){
121121
// No nodes are there in the tree till now
122122
return
123123
}
124-
this.root.visit()
124+
this.root.visit(output)
125125
}
126126

127127
// Start by searching the root
128128
search(val){
129-
constfound=this.root.search(val)
130-
if(found!==null){
131-
returnfound.value
129+
if(this.root){
130+
constfound=this.root.search(val)
131+
if(found!==null){
132+
returnfound.value
133+
}
132134
}
135+
133136
// not found
134137
returnnull
135138
}
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
import{Tree}from'../BinarySearchTree.js'
2+
3+
describe('Binary Search Tree',()=>{
4+
lettree
5+
6+
beforeEach(()=>{
7+
tree=newTree()
8+
tree.addValue(10)
9+
tree.addValue(5)
10+
tree.addValue(15)
11+
tree.addValue(3)
12+
tree.addValue(8)
13+
})
14+
15+
test('should add values to the tree',()=>{
16+
tree.addValue(12)
17+
18+
expect(tree.search(12)).toBe(12)
19+
expect(tree.search(5)).toBe(5)
20+
expect(tree.search(15)).toBe(15)
21+
})
22+
23+
test('should perform in-order traversal',()=>{
24+
constvalues=[]
25+
constoutput=(val)=>values.push(val)
26+
tree.traverse(output)
27+
expect(values).toEqual([3,5,8,10,15])
28+
})
29+
30+
test('should remove leaf nodes correctly',()=>{
31+
tree.removeValue(5)
32+
expect(tree.search(5)).toBeNull()
33+
})
34+
35+
test('should remove nodes with one child correctly',()=>{
36+
tree.addValue(12)
37+
tree.removeValue(15)
38+
39+
expect(tree.search(15)).toBeNull()
40+
expect(tree.search(12)).toBe(12)
41+
})
42+
43+
test('should remove nodes with two children correctly',()=>{
44+
tree.addValue(18)
45+
tree.removeValue(15)
46+
47+
expect(tree.search(15)).toBeNull()
48+
expect(tree.search(18)).toBe(18)
49+
})
50+
51+
test('should return null for non-existent values',()=>{
52+
expect(tree.search(20)).toBeNull()
53+
expect(tree.search(0)).toBeNull()
54+
})
55+
56+
test('should handle removal of root node correctly',()=>{
57+
tree.removeValue(10)
58+
expect(tree.search(10)).toBeNull()
59+
})
60+
61+
test('should handle empty tree gracefully',()=>{
62+
constnewTree=newTree()
63+
newTree.removeValue(22)// Should not throw
64+
expect(newTree.search(22)).toBeNull()
65+
})
66+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp