Skip to content

Commit 2a91840

Browse files
author
hojas
committed
BinaryTree
1 parent 4f9400c commit 2a91840

File tree

8 files changed

+201
-100
lines changed

8 files changed

+201
-100
lines changed

‎src/1-data-structures/4-tree/binary-tree/BalanceBinaryTree.test.ts‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { BinaryTreeNode } from './BinaryTreeNode'
3+
import { isBalancedBinaryTree } from './BalancedBinaryTree'
4+
5+
describe('balanced Binary Tree', () => {
6+
it('should return true for a balanced binary tree', () => {
7+
const root = new BinaryTreeNode(1)
8+
root.left = new BinaryTreeNode(2)
9+
root.right = new BinaryTreeNode(3)
10+
11+
root.left.left = new BinaryTreeNode(4)
12+
13+
expect(isBalancedBinaryTree(root)).toBe(true)
14+
})
15+
16+
it ('should return false for an unbalanced binary tree', () => {
17+
const root = new BinaryTreeNode(1)
18+
19+
root.left = new BinaryTreeNode(2)
20+
root.right = new BinaryTreeNode(3)
21+
22+
root.left.left = new BinaryTreeNode(4)
23+
root.left.right = new BinaryTreeNode(5)
24+
25+
root.right.left = new BinaryTreeNode(6)
26+
root.right.right = new BinaryTreeNode(7)
27+
28+
root.right = new BinaryTreeNode(8)
29+
root.right.left = new BinaryTreeNode(10)
30+
31+
root.right.left.left = new BinaryTreeNode(9)
32+
33+
expect(isBalancedBinaryTree(root)).toBe(false)
34+
})
35+
})

‎src/1-data-structures/4-tree/binary-tree/BalancedBinaryTree.ts‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
import type { BinaryTreeNode } from './BinaryTreeNode'
2+
import { getHeight } from './BinaryTree'
3+
4+
export function isBalancedBinaryTree(root: BinaryTreeNode | null): boolean {
5+
return getHeight(root) !== -1
6+
}

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

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { BinaryTreeNode } from './BinaryTreeNode'
3+
import { isBST } from './BinarySearchTree'
4+
5+
describe('binary Search Tree', () => {
6+
it('should return true for a valid BST', () => {
7+
const root = new BinaryTreeNode(4)
8+
root.left = new BinaryTreeNode(2)
9+
root.right = new BinaryTreeNode(6)
10+
11+
root.left.left = new BinaryTreeNode(1)
12+
root.left.right = new BinaryTreeNode(3)
13+
14+
root.right.left = new BinaryTreeNode(5)
15+
root.right.right = new BinaryTreeNode(7)
16+
17+
expect(isBST(root)).toBe(true)
18+
})
19+
20+
it('should return false for an invalid BST', () => {
21+
const root = new BinaryTreeNode(4)
22+
root.left = new BinaryTreeNode(2)
23+
root.right = new BinaryTreeNode(6)
24+
25+
root.left.left = new BinaryTreeNode(1)
26+
root.left.right = new BinaryTreeNode(3)
27+
28+
root.right.left = new BinaryTreeNode(5)
29+
root.right.right = new BinaryTreeNode(7)
30+
31+
root.right.right.left = new BinaryTreeNode(8) // invalid BST
32+
33+
expect(isBST(root)).toBe(false)
34+
})
35+
})

‎src/1-data-structures/4-tree/binary-tree/BinarySearchTree.ts‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
import type { BinaryTreeNode } from './BinaryTreeNode'
2+
3+
export function isBST(root: BinaryTreeNode | null, leftValue = -Infinity, rightValue = Infinity): boolean {
4+
if (root === null) {
5+
return true
6+
}
7+
8+
return leftValue < root.value
9+
&& root.value < rightValue
10+
&& isBST(root.left, leftValue, root.value)
11+
&& isBST(root.right, root.value, rightValue)
12+
}

‎src/1-data-structures/4-tree/binary-tree/BinaryTree.ts‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
import type { BinaryTreeNode } from './BinaryTreeNode.ts'
2+
3+
export function getHeight(root: BinaryTreeNode | null): number {
4+
if (root === null) {
5+
return 0
6+
}
7+
8+
const leftHeight = getHeight(root.left)
9+
if (leftHeight === -1) {
10+
return -1
11+
}
12+
13+
const rightHeight = getHeight(root.right)
14+
if (rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) {
15+
return -1
16+
}
17+
18+
return Math.max(leftHeight, rightHeight) + 1
19+
}

‎src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.ts‎

Lines changed: 0 additions & 85 deletions
Original file line numberDiff line numberDiff line change
@@ -9,88 +9,3 @@ export class BinaryTreeNode {
99
this.right = null
1010
}
1111
}
12-
13-
/**
14-
* Level order traversal of a binary tree.
15-
* @param root
16-
*/
17-
export function levelOrder(root: BinaryTreeNode | null) {
18-
if (!root) {
19-
return []
20-
}
21-
22-
const res: number[][] = []
23-
const q = [root]
24-
25-
while (q.length > 0) {
26-
const len = q.length
27-
const arr: number[] = []
28-
29-
for (let i = 0; i < len; i++) {
30-
const node = q.shift() as BinaryTreeNode
31-
arr.push(node.value)
32-
33-
if (node.left) {
34-
q.push(node.left)
35-
}
36-
if (node.right) {
37-
q.push(node.right)
38-
}
39-
}
40-
41-
res.push(arr)
42-
}
43-
44-
return res
45-
}
46-
47-
/**
48-
* Preorder traversal of a binary tree.
49-
* @param root
50-
* @param res
51-
*/
52-
export function preorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
53-
if (!root) {
54-
return res
55-
}
56-
57-
res.push(root.value)
58-
preorderTraversal(root.left, res)
59-
preorderTraversal(root.right, res)
60-
61-
return res
62-
}
63-
64-
/**
65-
* Inorder traversal of a binary tree.
66-
* @param root
67-
* @param res
68-
*/
69-
export function inorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
70-
if (!root) {
71-
return res
72-
}
73-
74-
inorderTraversal(root.left, res)
75-
res.push(root.value)
76-
inorderTraversal(root.right, res)
77-
78-
return res
79-
}
80-
81-
/**
82-
* Postorder traversal of a binary tree.
83-
* @param root
84-
* @param res
85-
*/
86-
export function postorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
87-
if (!root) {
88-
return res
89-
}
90-
91-
postorderTraversal(root.left, res)
92-
postorderTraversal(root.right, res)
93-
res.push(root.value)
94-
95-
return res
96-
}

src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.test.ts renamed to src/1-data-structures/4-tree/binary-tree/TraversalBinaryTree.test.ts

Lines changed: 8 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
import { describe, expect, it } from 'vitest'
2+
import { BinaryTreeNode } from './BinaryTreeNode'
23
import {
3-
BinaryTreeNode,
44
inorderTraversal,
55
levelOrder,
66
postorderTraversal,
77
preorderTraversal,
8-
} from './BinaryTreeNode'
8+
} from './TraversalBinaryTree'
99

1010
function createBinaryTree() {
1111
const root = new BinaryTreeNode(1)
@@ -19,19 +19,6 @@ function createBinaryTree() {
1919
}
2020

2121
describe('binaryTreeNode', () => {
22-
it('should create node', () => {
23-
const node = new BinaryTreeNode(1)
24-
expect(node.value).toBe(1)
25-
expect(node.left).toBeNull()
26-
expect(node.right).toBeNull()
27-
})
28-
29-
it('should level order traversal', () => {
30-
const root = createBinaryTree()
31-
const res = levelOrder(root)
32-
expect(res).toEqual([[1], [2, 3], [4, 5, 6, 7]])
33-
})
34-
3522
it('should preorderTraversal', () => {
3623
const root = createBinaryTree()
3724
const res = preorderTraversal(root)
@@ -49,4 +36,10 @@ describe('binaryTreeNode', () => {
4936
const res = postorderTraversal(root)
5037
expect(res).toEqual([4, 5, 2, 6, 7, 3, 1])
5138
})
39+
40+
it('should level order traversal', () => {
41+
const root = createBinaryTree()
42+
const res = levelOrder(root)
43+
expect(res).toEqual([[1], [2, 3], [4, 5, 6, 7]])
44+
})
5245
})

‎src/1-data-structures/4-tree/binary-tree/TraversalBinaryTree.ts‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
import type { BinaryTreeNode } from './BinaryTreeNode'
2+
3+
/**
4+
* Preorder traversal of a binary tree.
5+
* @param root
6+
* @param res
7+
*/
8+
export function preorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
9+
if (!root) {
10+
return res
11+
}
12+
13+
res.push(root.value)
14+
preorderTraversal(root.left, res)
15+
preorderTraversal(root.right, res)
16+
17+
return res
18+
}
19+
20+
/**
21+
* Inorder traversal of a binary tree.
22+
* @param root
23+
* @param res
24+
*/
25+
export function inorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
26+
if (!root) {
27+
return res
28+
}
29+
30+
inorderTraversal(root.left, res)
31+
res.push(root.value)
32+
inorderTraversal(root.right, res)
33+
34+
return res
35+
}
36+
37+
/**
38+
* Postorder traversal of a binary tree.
39+
* @param root
40+
* @param res
41+
*/
42+
export function postorderTraversal(root: BinaryTreeNode | null, res: number[] = []) {
43+
if (!root) {
44+
return res
45+
}
46+
47+
postorderTraversal(root.left, res)
48+
postorderTraversal(root.right, res)
49+
res.push(root.value)
50+
51+
return res
52+
}
53+
54+
/**
55+
* Level order traversal of a binary tree.
56+
* @param root
57+
*/
58+
export function levelOrder(root: BinaryTreeNode | null) {
59+
if (!root) {
60+
return []
61+
}
62+
63+
const res: number[][] = []
64+
const q = [root]
65+
66+
while (q.length > 0) {
67+
const len = q.length
68+
const arr: number[] = []
69+
70+
for (let i = 0; i < len; i++) {
71+
const node = q.shift() as BinaryTreeNode
72+
arr.push(node.value)
73+
74+
if (node.left) {
75+
q.push(node.left)
76+
}
77+
if (node.right) {
78+
q.push(node.right)
79+
}
80+
}
81+
82+
res.push(arr)
83+
}
84+
85+
return res
86+
}

0 commit comments

Comments
 (0)