javascript-data-structures/binarySearchTree.js at master · nicolasromer/javascript-data-structures · 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

getBinarySearchTree = (rootValue) => {
	const getNode = (value) => ({
		value,
		left: null,
		right: null
	});

	const root = getNode(rootValue);
	let size = 1;

	const subtreeInsert = (value, root) => {
		if (value > root.value) {
			if (root.right) {
				return subtreeInsert(value, root.right);
			} else {
				root.right = getNode(value);
			}
		} else {
			if (root.left) {
				return subtreeInsert(value, root.left);
			} else {
				root.left = getNode(value);
			}
		}
	}

	const subTreeFind = (value, node = root) => {
			if (value === node.value) return true;
			if (value < node.value && node.left) {
				return subTreeFind(value, node.left);
			} else if (value > node.value && node.right) {
				return subTreeFind(value, node.right);
			}
			return false
		}

	return {
		insert(value) {
			subtreeInsert(value, root);
			return root;
		},
		find(value) {
			return subTreeFind(value, root);
		}

	}
}