bst.js

/* Binary Search Tree */

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

class BST {
  constructor() {
    this.root = null;
  }
  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function(node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }
  findMin() {
    let current = this.root;
    while (current.left !== null) {
      current = current.left;
    }
    return current.data;
  }
  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }
  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }
  isPresent(data) {
    let current = this.root;
    while (current) {
      if (data === current.data) {
        return true;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
  remove(data) {
    const removeNode = function(node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // node has no children 
        if (node.left == null && node.right == null) {
          return null;
        }
        // node has no left child 
        if (node.left == null) {
          return node.right;
        }
        // node has no right child 
        if (node.right == null) {
          return node.left;
        }
        // node has two children 
        var tempNode = node.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    this.root = removeNode(this.root, data);
  }
  isBalanced() {
    return (this.findMinHeight() >= this.findMaxHeight() - 1)
  }
  findMinHeight(node = this.root) {
      if (node == null) {
          return -1;
      };
      let left = this.findMinHeight(node.left);
      let right = this.findMinHeight(node.right);
      if (left < right) {
          return left + 1;
      } else {
          return right + 1;
      };
  }
  findMaxHeight(node = this.root) {
      if (node == null) {
          return -1;
      };
      let left = this.findMaxHeight(node.left);
      let right = this.findMaxHeight(node.right);
      if (left > right) {
          return left + 1;
      } else {
          return right + 1;
      };
  }
  pathBetweenNodes(root, nodeA, nodeB) {
    // Function to check if there is a path from root  
    // to the given node. It also populates  
    // 'arr' with the given path  
    const getPath = (node, path, target) => {
      // if root is null  
      // there is no path  
      if (!node)
        return false;
    
      // push the node's value in 'arr'  
      path.push(node.data);  
    
      // if it is the required node  
      // return true  
      if (node.val == target)
        return true;
        
      // else check whether the required node lies  
      // in the left subtree or right subtree of  
      // the current node  
      if (getPath(node.left, path, target) || getPath(node.right, path, target))
        return true;
      // required node does not lie either in the  
      // left or right subtree of the current node  
      // Thus, remove current node's value from  
      // 'arr'and then return false  
      path.pop();  
      return false; 
    }
    // intersection
    let path1 = [];
    let path2 = [];

    getPath(root, path1, nodeA);
    getPath(root, path2, nodeB);

    let intersection = -1;
   
     // Get intersection point  
     int i = 0, j = 0;  
     while (i != path1.length || j != path2.length {  
         // Keep moving forward until no intersection  
         // is found  
         if (i == j && path1[i] == path2[i] {  
             i++;  
             j++;  
         }  
         else {  
             intersection = j - 1;  
             break;  
         }  
     }  
   
     // Print the required path  
     for ( i = path1.size() - 1; i > intersection; i--)  
         System.out.print( path1.get(i) + " "); 
   
     for ( i = intersection; i < path2.size(); i++)  
         System.out.print( path2.get(i) + " ");  
  },
  rootToLeafPaths(root) {
    if (!root) return null
    let res = [];
    const dfs = (node, path) => {
      if (path == "") path = node.val.toString();
      else
        path = `${path}->${node.val}`
      if (node.left == null && node.right == null) {
        res.push(path)
        return;
      }
      dfs(node.left, path);
      dfs(node.right, path);
    }
    dfs(root, "")
    return res;
  },
  inOrder() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traverseInOrder(node) {       
        node.left && traverseInOrder(node.left);
        result.push(node.data);
        node.right && traverseInOrder(node.right);
      }
      traverseInOrder(this.root);
      return result;
    };
  }
  preOrder() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traversePreOrder(node) {
        result.push(node.data);
        node.left && traversePreOrder(node.left);
        node.right && traversePreOrder(node.right);
      };
      traversePreOrder(this.root);
      return result;
    };
  }
  postOrder() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traversePostOrder(node) {
        node.left && traversePostOrder(node.left);
        node.right && traversePostOrder(node.right);
        result.push(node.data);
      };
      traversePostOrder(this.root);
      return result;
    }
  }
  greaterSumTree() {
    evaluateNode(null, root, 0);
    return root;
    var evaluateNode = function (parent, node, acc) {
        let finalAcc = 0;

        // Base case. We hit leaf nodes.
        if (node.right == null && node.left == null) {

            // Current node is a right child.
            if (node.val > parent.val)
                node.val += acc;

            // Current node is a left child.
            if (node.val < parent.val)
                node.val += parent.val;

            return node.val;
        }

        if (node.right != null) {
            node.val += evaluateNode(node, node.right, acc);;
            finalAcc = node.val;
        }

        if (node.left != null) {
            finalAcc = evaluateNode(node, node.left, node.val);;
        }

        return finalAcc;
    }
  },
  levelOrder() {
      let result = [];
      let Q = []; 
      if (this.root != null) {
          Q.push(this.root);
          while(Q.length > 0) {
              let node = Q.shift();
              result.push(node.data);
              if (node.left != null) {
                  Q.push(node.left);
              };
              if (node.right != null) {
                  Q.push(node.right);
              };
          };
          return result;
      } else {
          return null;
      };
  };
}



const bst = new BST();

bst.add(9);
bst.add(4);
bst.add(17);
bst.add(3);
bst.add(6);
bst.add(22);
bst.add(5);
bst.add(7);
bst.add(20);

console.log(bst.findMinHeight());
console.log(bst.findMaxHeight());
console.log(bst.isBalanced());
bst.add(10);
console.log(bst.findMinHeight());
console.log(bst.findMaxHeight());
console.log(bst.isBalanced());
console.log('inOrder: ' + bst.inOrder());
console.log('preOrder: ' + bst.preOrder());
console.log('postOrder: ' + bst.postOrder());

console.log('levelOrder: ' + bst.levelOrder());