CountLongestUniquePathBST.js

/* Author Aman Meghrajani - amanmeghrajaniatgmaildotcom */
/* Function to find the longest unique path in a Given BST with O(n) complexity */



/*
Utility Function - _longestUniquePath 
Input            - Tree object and a cache object to store path count
Output           - Maximum Path count
*/

const _longestUniquePath = (node, cache) => {
  
    /* Recursion control, return count when on leaf */
    if(!node) { return Object.keys(cache).length; }
    
    /* Add node's value as cache key, increment value in case of duplicates */
    cache[node.value] = cache[node.value] ? cache[node.value] + 1 : 1;
    
    /* Recurse over both children and get Maximum unqiue path count between left and right childredn */
    const longestPath = Math.max(_longestUniquePath(node.left, cache), _longestUniquePath(node.right, cache)); 
    
    /* Done with this node, decrement value */
    cache[node.value] = cache[node.value] - 1;
    
    /* If all duplicates processed for the current value, value will be 0 which is falsy in JS, remove from cache */
    if(!cache[node.value]) { delete cache[node.value]; }
    
    /* Divide & Conquer */
    return longestPath;
  
  }
  
  
  
  /*
  Exposed Function - longestUniquePath 
  Input            - Tree object
  Output           - integer with value equaling to number of nodes in the longest unique path of Tree
  */
  
  const longestUniquePath = (tree) => {
    if(!tree || !tree instanceof Tree) { return 0; }
    return _longestUniquePath(tree, {});
  }
  
  
  
  /*
  Object             - Tree, models a Binary Search Tree
  Constructor Input  - value : value of the current node, left : left Tree object, right : right Tree object 
  */
  
  function Tree( value, left, right ) {
      this.value = value;
      this.left  = typeof value === Tree ? left  : null;
      this.right = typeof value === Tree ? right : null;
      
      /* Instance Method to get count of longest unique path */
      this.countLongestUniquePath = () => longestUniquePath(this);
  }
  
  
  
  /*
  Simple Test
  */
  
  let tree             = new Tree(10);

  tree.left            = new Tree(100);
  tree.right           = new Tree(200);

  tree.left.left       = new Tree(600);
  tree.left.right      = new Tree(200);
  
  tree.right.left      = new Tree(100);
  tree.right.right     = new Tree(400);
  
  tree.left.left.left  = new Tree(800); 
  tree.left.left.right = new Tree(900);
  
  /* should win : Longest Path = 5 */
  tree.left.left.left.left = new Tree(99);
  
  let result = tree.countLongestUniquePath();
  console.log(result);