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

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(value) {
        let newNode = new Node(value);
        if(!this.root) {
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while(true) {
            if(value === current.value) return undefined;
            if(value < current.value) {
                if(!current.left) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(!current.right) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }
    find(value) {
        if(!this.root) return false;
        let current = this.root;
        let found = false;
        while(current && !found) {
            if(value < current.value) {
                current = current.left;
            } else if(value > current.value) {
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value) {
        if(!this.root) return false;
        let current = this.root;
        let found = false;
        while(current && !found) {
            if(value < current.value) {
                current = current.left;
            } else if(value > current.value) {
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
    BFS() {
        let queue = [];
        let data = [];
        let node = this.root;
        queue.push(node.value);
        while(queue.length) {
            node = queue.shift();
            data.push(node.value);
            if(node.left) {
                queue.push(node.left);
            }
            if(node.right) {
                queue.push(node.right);
            }
        }
        return data;
    }
    DFSPreOrder() {
        let data = [];
        let node = this.root;
        function traverse(node) {
            data.push(node.value);
            if(node.left) {
                traverse(node.left);
            }
            if(node.right) {
                traverse(node.right);
            }
        }
        traverse(node);
        return data;
    }
    DFSPostOrder() {
        let data = [];
        let node = this.root;
        function traverse(node) {
            if(node.left) {
                traverse(node.left);
            }
            if(node.right) {
                traverse(node.right);
            }
            data.push(node.value);
        }
        traverse(node);
        return data;
    }
    DFSInOrder() {
        let data = [];
        let node = this.root;
        function traverse(node) {
            if(node.left) {
                traverse(node.left);
            }
            data.push(node.value);
            if(node.right) {
                traverse(node.right);
            }
        }
        traverse(node);
        return data;
    }
}