1. Binary search tree (two conditions):

(1) There are at most two sub-nodes in the binary tree: one is the left node, the other is the right sub-node.
(2) Only values smaller than the parent node are allowed to be stored in the left node, while values larger (or equal to) are allowed in the right node.

2. Code Architecture:

It mainly includes insert, search, removce, traverse and other functions.

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;  //Left node
        this.right = null; //Right node
    }
    var root = null;    //Root node  
    /*
    Insert node:
    1,The tree is empty.
    2,Trees are not empty - > comparative (less than - > go left; greater than - > go right)
    */ 
    this.insert = function(value) {};
    //Search nodes (search for a specific value)
    this.search = function(value) {};
    //A Method of Finding the Minimum Key of a Tree
    this.min = function() {};
    //A Method of Finding the Maximum Key of a Tree
    this.max = function() {};
    /*
    Remove nodes:
    1,Simplest case: Remove leaf nodes
    2,Remove a node with only one child node
    3,Remove the node with two sub-nodes (replaced by the smallest node in the right subtree)
    */
    this.remove =function(value) {
    };
    //Traversing node
    this.traverse = function(callback) {};
    
    //Display tree
    this.getRoot = function() {};
}

3. Overall detailed code section

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //Root node  
    /*
    Insert node:
    1,The tree is empty.
    2,Trees are not empty - > comparative (less than - > go left; greater than - > go right)
    */ 
    this.insert = function(value) {
        var newNode = new Node(value);
        if(root == null) { //Empty tree          
            root = newNode;
        }else{//Trees are not empty.           
            insertNode(root, newNode);
        }
    };
    var insertNode = function(node, newNode) {
        if(newNode.value > node.value) {
            //Go right.
            if(node.right == null) {
                node.right = newNode;
            }else{
                insertNode(node.right, newNode);
            }   
        }else if(newNode.value < node.value) {
            //Go to the left.
            if(node.left == null) {
                node.left = newNode;
            }else{
                insertNode(node.left, newNode);
            }
        }
    };


    //Search nodes (search for a specific value)
    this.search = function(value) {
        return searchNode(root, value);
    };
    var searchNode = function(node, value) {
        if(node === null) {
            return false;
        }
        if(value < node.value) {
            return searchNode(node.left, value);
        }else if(value > node.value) {
            return searchNode(node.right, value);
        }else{
            return true;
        }
    };
   //A Method of Finding the Minimum Key of a Tree
   this.min = function() {
       return minNode(root);
   };
   var minNode = function(node) {
       if(node) {
           while(node && node.left !== null) {
               node = node.left;
           }
           return node.value;
       }
       return null;
   };
   //A Method of Finding the Maximum Key of a Tree
   this.max = function() {
       return maxNode(root);
   };
   var maxNode = function(node) {
       if(node) {
           while(node && node.right !== null) {
               node = node.right;
           }
           return node.value;
       }
       return null;
   };

    /*
    Remove nodes:
    1,Simplest case: Remove leaf nodes
    2,Remove a node with only one child node
    3,Remove the node with two sub-nodes (replaced by the smallest node in the right subtree)
    */
    this.remove =function(value) {
        root = removeNode(root, value);
    };
    var removeNode = function(node,value) {
        if( node == null) return null;
        if(node.value < value) {
            //Continue to look to the right
            node.right = removeNode(node.ritht , value);
            return node;
        }else if(node.value > value) {
            //Search left
            node.left = removeNode(node.left, value);
            return node;
        }else{
            //value == node.value
            //Execute the deletion process
            //Leaf Node Conditions
            if(node.left == null && node.right == null) {
                node = null;
                return node;
            }
            //Only one subnode condition
            if(node.left == null && node.right) {
                node = node.right;
                return node;     
            }else if(node.right == null && node.left){
                node = node.left;
                return node;
            }

            //There are two child nodes (replaced by the smallest node of the right subtree)
            var aux = findMinNode(node.right);   //aux is the smallest child found
            node.value = aux.value;
            node.right = removeNode(node.right, aux.value);
            return node;
        }
    };
    var findMinNode = function(node) {
        if(node == null) return null;
        while(node && node.left) {
            node = node.left
        }
        return node;
    };


    //Traversing node
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //(follow-up traversal) left-right middle; (middle-order traversal) left-right; (pre-order traversal) middle-left
        traverse(node.left, callback);
        traverse(node.right, callback);
        callback(node.value);
    };
    
    //Display tree
    this.getRoot = function() {
        return root;
    };
}

4. Code Function Verification Test

var t = new Tree;
var print = function(value) {
    console.log('value -',value)   
};

t.insert(11);
t.insert(8);
t.insert(4);
t.insert(9);
t.insert(3);
t.insert(5);

t.insert(9);
t.insert(12);

t.search(9); //true
t.remove(8);
t.min(); //3
t.max(); //12
t.traverse(print); 

5. Traversal Mode

Preorder traversal

• Sequential traversal is to access each node in the order that it takes precedence over the descendant nodes. One application of sequential traversal is to print a structured document.

11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};
preOrderTraverseNode The implementation of the method is as follows:
var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        callback(node.key); //{1}
        preOrderTraverseNode(node.left, callback); //{2}
        preOrderTraverseNode(node.right, callback); //{3}
    }
};

Sequential traversal

• Intermediate traversal is a traversal method of accessing all BST nodes in row order, that is, accessing all nodes in the order of minimum to maximum. One application of mid-order traversal is to sort trees.

3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root, callback); //{1}
};
var inOrderTraverseNode = function (node, callback) {
    if (node !== null) { //{2}
    inOrderTraverseNode(node.left, callback); //{3}
    callback(node.key); //{4}
    inOrderTraverseNode(node.right, callback); //{5}
    }
};

Post order traversal

• Later traversal is to access the descendant node of the node first, and then the node itself. One application of post-order traversal is to calculate the size of space occupied by all files in a directory and its subdirectories.

3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
postOrderTraverseNode The implementation of the method is as follows:
var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback); //{1}
        postOrderTraverseNode(node.right, callback); //{2}
        callback(node.key); //{3}
    }
};