Lowest Common Ancestor

lca.ts

console.clear();

class TNode {
  public left: TNode|undefined;
  public right: TNode|undefined;
  constructor(public value: number) {}
}

const root = new TNode(1)
const n2 = new TNode(2)
const n3 = new TNode(3)
const n4 = new TNode(4)
const n5 = new TNode(5)
const n6 = new TNode(6)

root.left = n3;
root.right = n2;
n3.left = n4;
n3.right = n6;
n6.right = n5;

/*
-----1-----
---3/ \2---
-4/ \6-----
       \5---
*/

class Stack<T> {
  private _data: Array<T> = [];

  constructor(arr: Array<T>) {
    this._data = arr ?? [];
  }

  add(value: T): void {
    this._data.push(value);
  }

  get pop(): T | undefined {
    return this._data.pop();
  }

  get pick(): T | undefined {
    return this._data[this._data.length - 1];
  }

  get isEmpty(): boolean {
    return this._data.length === 0;
  }

  get isNotEmpty(): boolean {
    return !this.isEmpty;
  }

  toString() {
    return this._data.toString();
  }
}

function valuePath(root: TNode|undefined, x: number): Stack<number> | undefined {
  if(!root) return undefined;
  if(root.value === x) {
      return new Stack([x]);
  }
  const leftPath = valuePath(root.left, x);

  if (leftPath != null) {
    leftPath.add(root.value);
    return leftPath;
  }
  const rightPath = valuePath(root.right, x);

  if (rightPath != null) {
    rightPath.add(root.value);
    return rightPath;
  }
  return undefined;
}


function lca(root: TNode|undefined, one: number, two: number): number|undefined {
  const f = valuePath(root, one);
  const s = valuePath(root, two);
  console.log('first: ' + f);
  console.log('second: ' + s);
  let result = undefined;

  while((f && f.isNotEmpty) && (s && s.isNotEmpty)) {
    const v1 = f.pop;
    const v2 = s.pop;
    if(v1 === v2) {
      result = v1;
    } else {
      break;
    }
  }
  return result;
}

console.log(lca(root, 4, 5));