Skip to content

Instantly share code, notes, and snippets.

@djleonskennedy
Created September 22, 2020 10:59
Show Gist options
  • Save djleonskennedy/a308c8838d5aa513922e1f5dbd97baf2 to your computer and use it in GitHub Desktop.
Save djleonskennedy/a308c8838d5aa513922e1f5dbd97baf2 to your computer and use it in GitHub Desktop.
Lowest Common Ancestor
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));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment