LCA

LCA.js

class BNode {
	constructor (value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}


	search(values) {
		let c = values.indexOf(this.data) >=0 ? 1 : 0;
		let lc = this.left ? this.left.search(values) : 0;
		let rc = this.right? this.right.search(values) : 0;
		return c + lc + rc;
	}


	searchLCA(values) {

		if (values.indexOf(this.data) >= 0) {
			return this;
		} 

		//search left tree
		if (this.left) {
			let leftCount = this.left.search(values);
			if (leftCount == values.length) {
				return this.left.searchLCA(values);
			}

			if (leftCount == 0 && this.right) {
				return this.right.searchLCA(values);
			}

			if (leftCount > 0 && leftCount < values.length) {
				return this;
			}
		}

		return "Not Found";
	}

}

let root = new BNode(0);

let l1 = new BNode(10);
let l2 = new BNode('A');

root.left = l1; root.right = l2;

let p1 = new BNode(100);
let p2 = new BNode(27);
l1.left = p1; l1.right = p2;

let p3 = new BNode("X");
let p4 = new BNode("YY");
l2.left = p3; l2.right = p4;

p4.left = new BNode("horse")

console.log(root.search(["X", "YY", "Z", 0]));
console.log(root.search(["A", 0, "C"]));
console.log(p4.search(["A"]));
console.log(p4.search(["YY"]));

console.log(root.searchLCA([100, 27]));
console.log(root.searchLCA(["horse", "X"]));
console.log(root.searchLCA(["A", "YY"]));


console.log("-----ROOT------");
console.log(root);

3
2
0
1
BNode {
  data: 10,
  left: BNode { data: 100, left: null, right: null },
  right: BNode { data: 27, left: null, right: null } }
BNode {
  data: 'A',
  left: BNode { data: 'X', left: null, right: null },
  right:
   BNode {
     data: 'YY',
     left: BNode { data: 'horse', left: null, right: null },
     right: null } }
BNode {
  data: 'A',
  left: BNode { data: 'X', left: null, right: null },
  right:
   BNode {
     data: 'YY',
     left: BNode { data: 'horse', left: null, right: null },
     right: null } }
-----ROOT------
BNode {
  data: 0,
  left:
   BNode {
     data: 10,
     left: BNode { data: 100, left: null, right: null },
     right: BNode { data: 27, left: null, right: null } },
  right:
   BNode {
     data: 'A',
     left: BNode { data: 'X', left: null, right: null },
     right: BNode { data: 'YY', left: [BNode], right: null } } }
[Finished in 0.1s]