Given the root node of a binary tree with n nodes, your task is to find the lowest common ancestor of two of its nodes, p and q.

lowest-common-ancestor.js

// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }

import { TreeNode } from "./ds_v1/BinaryTree.js";

class Solution {
  lowestCommonAncestor(root, p, q) {
    // if node is one of the nodes
    // we set "mid" 
    // but returned value is either left or right
    // Replace this placeholder return statement with your code
    // so 3 variables, left mid right
    const { found, result } = this.lowestCommonAncestorRec(root, p, q);
    return result;
  }

  lowestCommonAncestorRec(node, p, q) {
    if (node === null) {
      return { found: false };
    }

    // common ancestor: mid AND left, mid AND right, left AND right

    // mid - if this node is one of the nodes we're looking for
    const mid = node.data === p.data || node.data === q.data;

    // left - if node we're looking for is somewhere the left subtree
    const { found: left, result: leftResult } = this.lowestCommonAncestorRec(node.left, p, q);
    // right - if node we're looking for is somewhere in the right subtree
    const { found: right, result: rightResult } = this.lowestCommonAncestorRec(node.right, p, q);

    // didFindAncestor - whether or not any condition is fulfilled that makes current node the result
    const didFindAncestor = (mid && left) || (mid && right) || (left && right);

    // found - boolean indicating that we found the value somewhere in this tree
    // result - either this node, or a result from left or right subtree, if there is one
    return { found: left || right || mid, result: didFindAncestor ? node : (leftResult ?? rightResult ?? null) };
  }
}

export default Solution;

// tc: O(n)
// sc: O(h