Node.js Binary Search Tree(||) - Distance between nodes

Ejemplo de una clase de árbol binario de búsqueda agregando los métodos de distanceBetweenNodes y distanceFromAncestor para obtener la distancia entre nodos en un BST. Utiliza una clase nodo para guardar los datos de cada uno de los items almacenados en él.

Métodos a agregar

Obtener la distancia desde un nodo específico a un nodo ancestro.

distanceFromAncestor(currentAncestor, node) {
  if(!currentAncestor || currentAncestor.data === node) {
    return 0;
  }
  if(currentAncestor.data > node) {
    return 1 + this.distanceFromAncestor(currentAncestor.left, node);
  }
  if(currentAncestor.data < node) {
    return 1 + this.distanceFromAncestor(currentAncestor.right, node);
  }
}

Obtener la distancia entre nodos tomando en cuenta las dos siguientes consideraciones:

1. Si el argumento currentAncestor es nulo, entonces se tomará en cuenta el nodo raíz
2. el nodo 1 siempre debe ser más pequeño que el nodo 2.

distanceBetweenNodes(n1, n2, currentAncestor) {
  if(!currentAncestor) {
    currentAncestor = this.root;
  }
  if(n1 > n2){
    let temp = n2;
    n2 = n1;
    n1 = temp;
  }
  if(currentAncestor.data > n1 && currentAncestor.data > n2){
    return this.distanceBetweenNodes(currentAncestor.left, n1, n2);
  }
  if(currentAncestor.data < n1 && currentAncestor.data < n2) {
    return this.distanceBetweenNodes(currentAncestor.right, n1, n2);
  }
  if(currentAncestor.data >= n1 && currentAncestor.data <= n2) {
    return this.distanceFromAncestor(currentAncestor, n1) + this.distanceFromAncestor(currentAncestor, n2);
  }
}

Clase Binary Search Tree con métodos agregados

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    }
    return this.insert(data, node);
  }
  insert(data, node) {
    if (data < node.data) {
      if (!node.left) {
        node.left = new Node(data);
        return;
      } else {
        return this.insert(data, node.left);
      }
    } else if (data > node.data) {
      if (!node.right) {
        node.right = new Node(data);
        return;
      } else {
        return this.insert(data, node.right);
      }
    } else {
      return node;
    }
  }
  distanceFromAncestor(currentAncestor, node) {
    if (!currentAncestor || currentAncestor.data === node) {
      return 0;
    }
    if (currentAncestor.data > node) {
      return 1 + this.distanceFromAncestor(currentAncestor.left, node);
    }
    if (currentAncestor.data < node) {
      return 1 + this.distanceFromAncestor(currentAncestor.right, node);
    }
  }
  distanceBetweenNodes(n1, n2, currentAncestor) {
    if (!currentAncestor) {
      currentAncestor = this.root;
    }
    if (n1 > n2) {
      let temp = n2;
      n2 = n1;
      n1 = temp;
    }
    if (currentAncestor.data > n1 && currentAncestor.data > n2) {
      return this.distanceBetweenNodes(n1, n2, currentAncestor.left);
    }
    if (currentAncestor.data < n1 && currentAncestor.data < n2) {
      return this.distanceBetweenNodes(n1, n2, currentAncestor.right);
    }
    if (currentAncestor.data >= n1 && currentAncestor.data <= n2) {
      return (
        this.distanceFromAncestor(currentAncestor, n1) +
        this.distanceFromAncestor(currentAncestor, n2)
      );
    }
  }
}

Implementación

let bst = new BinarySearchTree();
bst.add(8);
bst.add(3);
bst.add(4);
bst.add(10);
console.log(bst.distanceBetweenNodes(10, 8));