algorithms-in-javascript/binary-search-tree.js at master · veeracs/algorithms-in-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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//  Binary search tree
//  Time Complexity - log n
function BinarySearchTree() {
    this.root = null;
    return this;
}

BinarySearchTree.prototype = {
    constructor: BinarySearchTree,
    insert: function insert(value, currNode) {
        //  1. initialize the node to be inserted
        var node = {
            value: value,
            left: null,
            right: null
        };
        //  2. initialize the root node
        if (!this.root) {
            this.root = node;
            return this;
        }
        //  3. determine currNode (helps recursively navigate the tree for node insertion)
        currNode = currNode || this.root;
        //  4. determine the insert key (where to insert the node)
        var insertKey = "right";
        if (value < currNode.value) {
            insertKey = "left";
        }
        //  5. insert the node if it doesn't exist
        if (!currNode[insertKey]) {
            currNode[insertKey] = node;
        } else {
            //  6. if the left/right nodes exist, traverse the binary tree via recursion
            this.insert(value, currNode[insertKey]);
        }

        return this;
    },
    preOrder: function preOrder(currNode) {
        //  root -> left -> right
        // print the currNode
        // recurse the left subtree
        // recurse the right subtree
        currNode = currNode || this.root;
        if (!currNode) {
            return;
        }
        console.log(currNode.value);
        if (currNode.left) {
            preOrder(currNode.left);
        }
        if (currNode.right) {
            preOrder(currNode.right);
        }
    },
    inOrder: function inOrder(currNode) {
        // left -> root -> right
        // recurse the left subtree
        // print the currNode
        // recurse the right subtree
        currNode = currNode || this.root;
        if (!currNode) {
            return;
        }
        if (currNode.left) {
            inOrder(currNode.left);
        }
        console.log(currNode.value);
        if (currNode.right) {
            inOrder(currNode.right);
        }
    },
    postOrder: function postOrder(currNode) {
        // left -> right -> root
        // recurse the left subtree
        // recurse the right subtree
        // print the currNode
        currNode = currNode || this.root;
        if (!currNode) {
            return;
        }
        if (currNode.left) {
            postOrder(currNode.left);
        }
        if (currNode.right) {
            postOrder(currNode.right);
        }
        console.log(currNode.value);
    },
    levelOrder: function levelOrder() {
        //  Level-order traversal is Breadth First Search Traversal
        //  For each node, first the node is visited and then it's child nodes are put in FIFO
        var queue = [];
        var currNode = this.root;

        while (currNode) {
            //  log value of root node
            console.log(currNode.value);
            //  push it's children into a queue
            if (currNode.left) queue.push(currNode.left);
            if (currNode.right) queue.push(currNode.right);
            //  dequeue each child node from the queue
            currNode = queue.shift();
        }
    }
};

var btree = new BinarySearchTree();
btree.insert(100).insert(20).insert(120).insert(12);
//  print nodes with breadth first search
btree.levelOrder();
btree.preOrder();
btree.inOrder();
btree.postOrder();