data-structures-and-algorithms-javascript/binary-tree.js at main · NixLoar/data-structures-and-algorithms-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
77
78
79
80
81
82
83
84
85
86
87
88
89
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        if (!this.root) {
            this.root = new TreeNode(value);
        } else {
            this._insertRecursive(this.root, value);
        }
    }

    _insertRecursive(node, value) {
        if (value < node.value) {
            if (!node.left) {
                node.left = new TreeNode(value);
            } else {
                this._insertRecursive(node.left, value);
            }
        } else {
            if (!node.right) {
                node.right = new TreeNode(value);
            } else {
                this._insertRecursive(node.right, value);
            }
        }
    }

    search(value) {
        return this._searchRecursive(this.root, value);
    }

    _searchRecursive(node, value) {
        if (!node) {
            return false;
        }
        if (value === node.value) {
            return true;
        }
        if (value < node.value) {
            return this._searchRecursive(node.left, value);
        } else {
            return this._searchRecursive(node.right, value);
        }
    }

    inorderTraversal() {
        const result = [];
        this._inorderRecursive(this.root, result);
        return result;
    }

    _inorderRecursive(node, result) {
        if (node) {
            this._inorderRecursive(node.left, result);
            result.push(node.value);
            this._inorderRecursive(node.right, result);
        }
    }

    toString() {
        return "In-order: " + this.inorderTraversal().join(", ");
    }
}

// Example

const tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);

console.log(tree.toString());
console.log(`Search 4: ${tree.search(4)}`);
console.log(`Search 10: ${tree.search(10)}`);
console.log(`Inorder Traversal: ${tree.inorderTraversal()}`);