Lowest Ancestor

lowestAncestor.js

  class Node  {
	constructor(value) {
		this.value = value;
		this.children = [];
	}

	add(child) {
		this.children.push(child);
	}

	print(level=0) {
		let indent = "";
		for (let i = 0; i < level * 2; i++) {
			indent += " ";
		}
		process.stdout.write(`${indent}value : ${this.value} \n`);

		if(this.children.length > 0) {
			process.stdout.write(`${indent}children ↓↓ \n`);
			this.children.forEach(child => {
				child.print(level+1);
			});
		}

	}

	printPath(value) {
		let path = [];
		if (this.hasPath(value, path)) {
			return path.map(step => step.value).join(" -> ");
		} else {
			return "No Path Found";
		}
	}

	hasPath(value, opt_path) {
		let path = opt_path || [];

		function hasPathImpl(node, value, path) {
			if (!node) {
				return false;
			}
			path.push(node);
			if (node.value == value) {
				return true;
			}

			let bool = false;
			for(let i = 0; i < node.children.length; i++) {
				bool = bool || hasPathImpl(node.children[i], value, path);
			}

			if (bool) { return true; }

			path.pop();
			return false;
		}

		return hasPathImpl(this, value, path);
	}

	lowestAncestor(value1, value2) {
		let path1 = [];
		let path2 = [];

		if (!this.hasPath(value1, path1) || !this.hasPath(value2, path2)) {
			return "Not Both Values are in the tree";
		}
		

		let l = Math.min(path1.length, path2.length);
		let pointer = 0;
		while(pointer < l) {
			if (path1[pointer] == path2[pointer]) {
				pointer++;
			} else {
				break;
			}
		}

		return path1[pointer - 1].value;
	}
	
}

value : 0 
children ↓↓ 
  value : 10 
  children ↓↓ 
    value : A 
    value : B 
  value : 100 
  value : 500 
  children ↓↓ 
    value : X 
    children ↓↓ 
      value : horse 
      value : rabbit 
    value : YY 
No Path Found
0 -> 500 -> X -> horse
0 -> 500 -> X -> rabbit
X
500
0
Not Both Values are in the tree
[Finished in 0.1s]