BST_Traversal

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

class BST {
    constructor() {
        this.root = null;
    }
    
    lookup(value) {
        return this._findValue(this.root, value);
    }
    
    insert(value) {
        const newNode = new Node(value);
        if(this.root === null) {
            this.root = newNode;
        }
        else {
            this._createNewLeaf(this.root, newNode);
        }
    }
    
    traverse(node) {
        const tree = { value: node.value };
        tree.left = node.left === null ? null : traverse(node.left);
        tree.right = node.right === null ? null : traverse(node.right);
        return tree;
    }
    
    remove(value) {
        const node = this.lookup(value)
        if(!node) {
            return false;
        }
        const parent = this._findParent(this.root, node.value)
        //check if node has no children
        if(node.left === null && node.right === null) {
            if(value < parent.value) {
                parent.left = null;
            }
            else {
                parent.right = null;
            }
        }
        //check if node has 1 child and its to the right
        else if(!node.left) {
            //check if root
            if(node == parent) {
                this.root = node.right;
                return;
            }
            if(value < parent.value) {
                parent.left = node.right;
            }
            else {
                parent.right = node.right;
            }
        }
        //check if node has 1 child and its to the left
        else if(!node.right) {
            //check if root
            if(node == parent) {
                this.root = node.left;
                return;
            }
            if(value < parent.value) {
                parent.left = node.left;
            }
            else {
                parent.right = node.left;
            }
        }
        //node has two children
        else { 
            const successor = this.findMin(node.right);
            const successorParent = this._findParent(parent, successor.value);
            if(successor.right) {
                successorParent.left = successor.right;
            }
            else {
                successorParent.left = null;
            }
            successor.left = node.left;
            successor.right = node.right;
            //check if root
            if(node == parent) {
                this.root = successor;
                return;
            }
            if(value < parent.value) {
                parent.left = successor;
            }
            else {
                parent.right = succ0essor;
            }
        }
    }
    
    findMin(node) {
        let currentNode = node;
        while(currentNode.left !== null) {
            currentNode = currentNode.left;
        }
        return currentNode;
    }
    
    BFS() {
        let list = [];
        let queue = [];
        queue.push(this.root);
        
        while(queue.length > 0) {
            let currentNode = queue.shift();
            list.push(currentNode.value);
            
            if(currentNode.left) {
                queue.push(currentNode.left);
            }
            
            if(currentNode.right) {
                queue.push(currentNode.right);
            }
        }
        return list;
    }
    
    BFSr(queue, list) {
        if (!queue.length) {
            return list;
        }
        let currentNode = queue.shift();
        list.push(currentNode.value);
        
        if(currentNode.left) {
            queue.push(currentNode.left);
        }
        
        if(currentNode.right) {
            queue.push(currentNode.right);
        }
        
        return this.BFSr(queue, list);
    }
    
    inOrder() {
        return this.traverseInOrder(this.root, []);
    }
    
    preOrder() {
        return this.traversePreOrder(this.root, []);
    }
    
    postOrder() {
        return this.traversePostOrder(this.root, []);
    }
    
    traverseInOrder(node, list) {
        if(node.left) {
            this.traverseInOrder(node.left, list);
        }
        list.push(node.value);
        
        if(node.right) {
            this.traverseInOrder(node.right, list);
        }
        return list;
    }
    
    traversePreOrder(node, list) {
        list.push(node.value);
        
        if(node.left) {
            this.traversePreOrder(node.left, list);
        }
        
        if(node.right) {
            this.traversePreOrder(node.right, list);
        }
        return list;
    }
    
    traversePostOrder(node, list) {
        if(node.left) {
            this.traversePostOrder(node.left, list);
        }
        
        if(node.right) {
            this.traversePostOrder(node.right, list);
        }
        
        list.push(node.value);
        return list;
    }
    
    _findParent(node, value) {
        if(value == node.value) {
            //root node
            return node;
        }
        if(value > node.value) {
            if(value == node.right.value) {
                return node;
            }
            return this._findParent(node.right, value);
        }
        else {
            if(value == node.left.value) {
                return node;
            }
            return this._findParent(node.left, value);
        }
    }
    _createNewLeaf(node, newNode) {
        if(newNode.value > node.value) {
            if(node.right !== null) {
                this._createNewLeaf(node.right, newNode);
            }
            else {
                node.right = newNode;
            }
        }
        else {
            if(node.left !== null) {
                this._createNewLeaf(node.left, newNode);
            }
            else {
                node.left = newNode;
            }
        }
    }
    
    _findValue(node, value) {
        if(node === null || value == node.value) {
            return node;
        } 
        if(value > node.value) {
           return this._findValue(node.right, value);
        }
        else {
            return this._findValue(node.left, value);
        }
    }
}

const bst = new BST();
bst.insert(9);
bst.insert(4);
bst.insert(6);
bst.insert(20);
bst.insert(170);
bst.insert(15);
bst.insert(1);
//console.log(bst.lookup(6));
//console.log(JSON.stringify(traverse(bst.root)));
//console.log(bst.BFSr([bst.root], []));
console.log(bst.inOrder());
console.log(bst.preOrder());
console.log(bst.postOrder());
console.log(bst);
//console.log(JSON.stringify(traverse(bst.root)));


function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}