SOURCE

class Node {
    constructor(data) {
        this.data = data
        this.left = null
        this.right = null
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null
    }

    insert (data) {
        const newNode = new Node(data)
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    insertNode (node, newNode) {
        // if the data is less than the node. data move left of the tree
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left, newNode)
            }
        } else {
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right, newNode)
            }
        }
    }

    remove (data) {
        this.root = this.removeNode(this.root, data)
    }

    removeNode (node, key) {
        if (node === null) {
            return null
        } else if (key < node.data) {
            node.left = this.removeNode(node.left, key)
            return node
        } else if (key > node.data) {
            node.right = this.removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }

            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.left
                return node
            }

            let aux = this.findMinNode(node.right)
            node.data = aux.data
            node.right = this.removeNode(node.right, aux.data)
            return node
        }
    }

    // helper function

    findMinNode () {
        if (node.left) {
            return node
        } else {
            return this.findMinNode(node.left)
        }
    }

    getRootNode () {
        return this.root
    }

    inorder (node) {
        if (node != null) {
            this.inorder(node.left)
            console.log(node.data)
            this.inorder(node.right)
        }
    }

    preorder (node) {
        if (node != null) {
            console.log(node.data)
            this.preorder(node.left)
            this.preorder(node.right)
        }
    }

    postorder (node) {
        if (node != null) {
            this.postorder(node.left)
            this.postorder(node.right)
            console.log(node.data)
        }
    }

    search (node, data) {
        if (node === null) {
            return null
        } else if (data < node.data) {
            return this.search(node.left, data)
        } else if (data > node.data) {
            return this.search(node.right, data)
        } else {
            return node
        }
    }
}

const BST = new BinarySearchTree()
BST.insert(15);
BST.insert(25);
BST.insert(10);
BST.insert(7);
BST.insert(22);
BST.insert(17);
BST.insert(13);
BST.insert(5);
BST.insert(9);
BST.insert(27);

//          15
//         /  \
//        10   25
//       / \   / \
//      7  13 22  27
//     / \    /
//    5   9  17

// BST.inorder(BST.getRootNode())

// BST.preorder(BST.getRootNode())

// BST.postorder(BST.getRootNode())


// 非递归先序
const preOrder = (node) => {
    
}


const w = (node) => {
    if (node.data) {
        let queue = []
        queue.push(node) 
        while (queue.length) {
            node = queue.shift()
            console.log(node.data)
            if (node.left) {
                queue.push(node.left)
            }
             if (node.right) {
                queue.push(node.right)
            }
        }
    }
}

// console.log(w(BST.getRootNode()))

const getFloor = (node) => {
    if (node && node.data) {
        let queue = []
        queue.push(node)
        let levelMap = new Map()
        levelMap.set(node, 1)
        let curLevel = 1
        let curLevelNodes = 0
        let max = -Infinity
        while(queue.length) {
            let cur = queue.shift()
            let curNodeLevel = levelMap.get(cur)
            if (curNodeLevel === curLevel) {
                curLevelNodes++
            } else {
                max = Math.max(max, curLevelNodes)
                curLevel++
                curLevelNodes = 1
            }

            if (cur.left) {
                levelMap.set(cur.left, curNodeLevel + 1)
                queue.push(cur.left)
            }
             if (cur.right) {
                levelMap.set(cur.right, curNodeLevel + 1)
                queue.push(cur.right)
            }
        }
        console.log(max)
    }
}

getFloor(BST.getRootNode())


const getFloor2 = (node) => {
    if (node && node.data) {
        let queue = []
        queue.push(node)
        let curNodeEnd = node
        let nextNodeEnd = node
        let curLevelNodes = 0
        let max = -Infinity
        while(queue.length) {
            let cur = queue.shift()
            if(cur != curNodeEnd) {
                curLevelNodes++
            } else {
                max = Math.max(max, curLevelNodes)
                curNodeEnd = nextNodeEnd
                curLevelNodes = 0
            }

            if (cur.left) {
                nextNodeEnd = cur.left
                queue.push(cur.left)
            }
             if (cur.right) {
                nextNodeEnd = cur.right
                queue.push(cur.right)
            }
        }
        console.log(max)
    }
}

getFloor2(BST.getRootNode())