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";
	}

}

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]