Skip to content

Commit df57c62

Browse files
hojashojas
committed
BinaryTree
1 parent 0370d4e commit df57c62

File tree

5 files changed

+508
-2
lines changed

5 files changed

+508
-2
lines changed

‎README.md‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,10 @@
22

33
## Data Structures
44

5-
- Linked List
6-
- Doubly Linked List
5+
- [Linked List](https://github.com/hojas/typescript-algorithms/tree/main/src/data-structures/linked-list)
6+
- [Doubly Linked List](https://github.com/hojas/typescript-algorithms/tree/main/src/data-structures/doubly-linked-list)
7+
- [Stack](https://github.com/hojas/typescript-algorithms/tree/main/src/data-structures/stack)
8+
- [Queue](https://github.com/hojas/typescript-algorithms/tree/main/src/data-structures/queue)
9+
- [Tree](https://github.com/hojas/typescript-algorithms/tree/main/src/data-structures/tree)
710

811
## Algorithms

‎src/data-structures/tree/binary-search-tree/BinarySearchTree.test.ts‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { BinarySearchTree } from './BinarySearchTree'
3+
4+
describe('binarySearchTree', () => {
5+
it('should create binary search tree', () => {
6+
const bst = new BinarySearchTree()
7+
8+
expect(bst).toBeDefined()
9+
expect(bst.root).toBeDefined()
10+
expect(bst.root.value).toBeNull()
11+
expect(bst.root.left).toBeNull()
12+
expect(bst.root.right).toBeNull()
13+
})
14+
15+
it('should insert values', () => {
16+
const bst = new BinarySearchTree()
17+
18+
const insertedNode1 = bst.insert(10)
19+
const insertedNode2 = bst.insert(20)
20+
bst.insert(5)
21+
22+
expect(bst.toString()).toBe('5,10,20')
23+
expect(insertedNode1.value).toBe(10)
24+
expect(insertedNode2.value).toBe(20)
25+
})
26+
27+
it('should check if value exists', () => {
28+
const bst = new BinarySearchTree()
29+
30+
bst.insert(10)
31+
bst.insert(20)
32+
bst.insert(5)
33+
34+
expect(bst.contains(20)).toBe(true)
35+
expect(bst.contains(40)).toBe(false)
36+
})
37+
38+
it('should remove nodes', () => {
39+
const bst = new BinarySearchTree()
40+
41+
bst.insert(10)
42+
bst.insert(20)
43+
bst.insert(5)
44+
45+
expect(bst.toString()).toBe('5,10,20')
46+
47+
const removed1 = bst.remove(5)
48+
expect(bst.toString()).toBe('10,20')
49+
expect(removed1).toBe(true)
50+
51+
const removed2 = bst.remove(20)
52+
expect(bst.toString()).toBe('10')
53+
expect(removed2).toBe(true)
54+
})
55+
56+
it('should be traversed to sorted array', () => {
57+
const bst = new BinarySearchTree()
58+
59+
bst.insert(10)
60+
bst.insert(-10)
61+
bst.insert(20)
62+
bst.insert(-20)
63+
bst.insert(25)
64+
bst.insert(6)
65+
66+
expect(bst.toString()).toBe('-20,-10,6,10,20,25')
67+
expect(bst.root.height).toBe(2)
68+
69+
bst.insert(4)
70+
71+
expect(bst.toString()).toBe('-20,-10,4,6,10,20,25')
72+
expect(bst.root.height).toBe(3)
73+
})
74+
})

‎src/data-structures/tree/binary-search-tree/BinarySearchTree.ts‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
import { BinaryTreeNode } from '../binary-tree/BinaryTreeNode'
2+
3+
export class BinarySearchTreeNode extends BinaryTreeNode {
4+
constructor(value: number | null) {
5+
super(value)
6+
}
7+
8+
insert(value: number) {
9+
if (this.value === null) {
10+
this.value = value
11+
return this
12+
}
13+
14+
if (value < this.value) {
15+
if (this.left)
16+
return this.left.insert(value)
17+
18+
const newNode = new BinarySearchTreeNode(value)
19+
this.setLeft(newNode)
20+
return newNode
21+
}
22+
23+
if (value > this.value) {
24+
if (this.right)
25+
return this.right.insert(value)
26+
27+
const newNode = new BinarySearchTreeNode(value)
28+
this.setRight(newNode)
29+
return newNode
30+
}
31+
32+
return this
33+
}
34+
35+
find(value: number) {
36+
if (this.value === null)
37+
return null
38+
39+
if (this.value === value)
40+
return this
41+
42+
if (value < this.value && this.left)
43+
return this.left.find(value)
44+
45+
if (value > this.value && this.right)
46+
return this.right.find(value)
47+
48+
return null
49+
}
50+
51+
contains(value: number) {
52+
return !!this.find(value)
53+
}
54+
55+
remove(value: number) {
56+
const nodeToRemove = this.find(value)
57+
58+
// node not found
59+
if (!nodeToRemove)
60+
throw new Error('Item not found in the tree')
61+
62+
const { parent } = nodeToRemove
63+
64+
// node has no children
65+
if (!nodeToRemove.left && !nodeToRemove.right) {
66+
if (parent)
67+
parent.removeChild(nodeToRemove)
68+
else
69+
// node is root
70+
nodeToRemove.setValue(null)
71+
}
72+
// node has both children
73+
else if (nodeToRemove.left && nodeToRemove.right) {
74+
// find next bigger value (minimum value in the right branch)
75+
// and replace current value node with that next bigger value
76+
const nextBiggerNode = nodeToRemove.right.findMin()
77+
if (nextBiggerNode !== nodeToRemove.right) {
78+
this.remove(nextBiggerNode.value)
79+
nodeToRemove.setValue(nextBiggerNode.value)
80+
}
81+
else {
82+
nodeToRemove.setValue(nodeToRemove.right.value)
83+
nodeToRemove.setRight(nodeToRemove.right.right)
84+
}
85+
}
86+
else {
87+
const childNode = nodeToRemove.left || nodeToRemove.right
88+
if (parent)
89+
parent.replaceChild(nodeToRemove, childNode)
90+
else
91+
BinaryTreeNode.copyNode(childNode, nodeToRemove)
92+
}
93+
94+
nodeToRemove.parent = null
95+
return true
96+
}
97+
98+
findMin() {
99+
return this.left ? this.left.findMin() : this
100+
}
101+
}
102+
103+
export class BinarySearchTree {
104+
root: BinarySearchTreeNode
105+
106+
constructor() {
107+
this.root = new BinarySearchTreeNode(null)
108+
}
109+
110+
insert(value: number) {
111+
return this.root.insert(value)
112+
}
113+
114+
contains(value: number) {
115+
return this.root.contains(value)
116+
}
117+
118+
remove(value: number) {
119+
return this.root.remove(value)
120+
}
121+
122+
toString() {
123+
return this.root.toString()
124+
}
125+
}

‎src/data-structures/tree/binary-tree/BinaryTreeNode.test.ts‎

Lines changed: 185 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,185 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { BinaryTreeNode } from './BinaryTreeNode'
3+
4+
describe('binaryTreeNode', () => {
5+
it('should create node', () => {
6+
const node = new BinaryTreeNode()
7+
8+
expect(node).toBeDefined()
9+
10+
expect(node.value).toBeNull()
11+
expect(node.left).toBeNull()
12+
expect(node.right).toBeNull()
13+
14+
const leftNode = new BinaryTreeNode(1)
15+
const rightNode = new BinaryTreeNode(3)
16+
const rootNode = new BinaryTreeNode(2)
17+
18+
rootNode
19+
.setLeft(leftNode)
20+
.setRight(rightNode)
21+
22+
expect(rootNode.value).toBe(2)
23+
expect(rootNode.left?.value).toBe(1)
24+
expect(rootNode.right?.value).toBe(3)
25+
})
26+
27+
it('should set parent', () => {
28+
const leftNode = new BinaryTreeNode(1)
29+
const rightNode = new BinaryTreeNode(3)
30+
const rootNode = new BinaryTreeNode(2)
31+
32+
rootNode
33+
.setLeft(leftNode)
34+
.setRight(rightNode)
35+
36+
expect(rootNode.parent).toBeNull()
37+
expect(rootNode.left?.parent?.value).toBe(2)
38+
expect(rootNode.right?.parent?.value).toBe(2)
39+
expect(rootNode.left?.parent).toEqual(rootNode)
40+
expect(rootNode.right?.parent).toEqual(rootNode)
41+
})
42+
43+
it('should traverse node', () => {
44+
const leftNode = new BinaryTreeNode(1)
45+
const rightNode = new BinaryTreeNode(3)
46+
const rootNode = new BinaryTreeNode(2)
47+
48+
rootNode
49+
.setLeft(leftNode)
50+
.setRight(rightNode)
51+
52+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])
53+
expect(rootNode.toString()).toBe('1,2,3')
54+
})
55+
56+
it('should remove child node', () => {
57+
const leftNode = new BinaryTreeNode(1)
58+
const rightNode = new BinaryTreeNode(3)
59+
const rootNode = new BinaryTreeNode(2)
60+
61+
rootNode
62+
.setLeft(leftNode)
63+
.setRight(rightNode)
64+
65+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])
66+
67+
expect(rootNode.removeChild(rootNode.left!)).toBe(true)
68+
expect(rootNode.traverseInOrder()).toEqual([2, 3])
69+
70+
expect(rootNode.removeChild(rootNode.right!)).toBe(true)
71+
expect(rootNode.traverseInOrder()).toEqual([2])
72+
73+
expect(rootNode.removeChild(rootNode.right!)).toBe(false)
74+
expect(rootNode.traverseInOrder()).toEqual([2])
75+
})
76+
77+
it('should replace child node', () => {
78+
const leftNode = new BinaryTreeNode(1)
79+
const rightNode = new BinaryTreeNode(3)
80+
const rootNode = new BinaryTreeNode(2)
81+
82+
rootNode
83+
.setLeft(leftNode)
84+
.setRight(rightNode)
85+
86+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 3])
87+
88+
const replacementNode = new BinaryTreeNode(5)
89+
rightNode.setRight(replacementNode)
90+
91+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 3, 5])
92+
93+
expect(rootNode.replaceChild(rootNode.right!, rootNode.right!.right!)).toBe(true)
94+
expect(rootNode.right!.value).toBe(5)
95+
expect(rootNode.right!.right).toBeNull()
96+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])
97+
98+
expect(rootNode.replaceChild(rootNode.right!, rootNode.right!.right!)).toBe(false)
99+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])
100+
101+
expect(rootNode.replaceChild(rootNode.right!, replacementNode)).toBe(true)
102+
expect(rootNode.traverseInOrder()).toEqual([1, 2, 5])
103+
104+
expect(rootNode.replaceChild(rootNode.left!, replacementNode)).toBe(true)
105+
expect(rootNode.traverseInOrder()).toEqual([5, 2, 5])
106+
107+
expect(rootNode.replaceChild(new BinaryTreeNode(), new BinaryTreeNode())).toBe(false)
108+
})
109+
110+
it('should calculate node height', () => {
111+
const root = new BinaryTreeNode(1)
112+
const left = new BinaryTreeNode(3)
113+
const right = new BinaryTreeNode(2)
114+
const grandLeft = new BinaryTreeNode(5)
115+
const grandRight = new BinaryTreeNode(6)
116+
const grandGrandLeft = new BinaryTreeNode(7)
117+
118+
expect(root.height).toBe(0)
119+
expect(root.balanceFactor).toBe(0)
120+
121+
root
122+
.setLeft(left)
123+
.setRight(right)
124+
125+
expect(root.height).toBe(1)
126+
expect(left.height).toBe(0)
127+
expect(root.balanceFactor).toBe(0)
128+
129+
left
130+
.setLeft(grandLeft)
131+
.setRight(grandRight)
132+
133+
expect(root.height).toBe(2)
134+
expect(left.height).toBe(1)
135+
expect(grandLeft.height).toBe(0)
136+
expect(grandRight.height).toBe(0)
137+
expect(root.balanceFactor).toBe(1)
138+
139+
grandLeft.setLeft(grandGrandLeft)
140+
141+
expect(root.height).toBe(3)
142+
expect(left.height).toBe(2)
143+
expect(grandLeft.height).toBe(1)
144+
expect(grandRight.height).toBe(0)
145+
expect(grandGrandLeft.height).toBe(0)
146+
expect(root.balanceFactor).toBe(2)
147+
})
148+
149+
it('should calculate node height for right nodes as well', () => {
150+
const root = new BinaryTreeNode(1)
151+
const right = new BinaryTreeNode(2)
152+
153+
root.setRight(right)
154+
155+
expect(root.height).toBe(1)
156+
expect(right.height).toBe(0)
157+
expect(root.balanceFactor).toBe(-1)
158+
})
159+
160+
it('should set null for left and right node', () => {
161+
const root = new BinaryTreeNode(2)
162+
const left = new BinaryTreeNode(1)
163+
const right = new BinaryTreeNode(3)
164+
165+
root.setLeft(left)
166+
root.setRight(right)
167+
168+
expect(root.left?.value).toBe(1)
169+
expect(root.right?.value).toBe(3)
170+
171+
root.setLeft(null)
172+
root.setRight(null)
173+
174+
expect(root.left).toBeNull()
175+
expect(root.right).toBeNull()
176+
})
177+
178+
it('should be possible to set node values', () => {
179+
const node = new BinaryTreeNode(1)
180+
expect(node.value).toBe(1)
181+
182+
node.setValue(2)
183+
expect(node.value).toBe(2)
184+
})
185+
})

0 commit comments

Comments
 (0)