Lowest Common Ancestor of a Binary Search Tree - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const LCA = 'lca', LCA_COLOR = 'green';

function visMainFunction(treeInput, pInput, qInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const root = convertInputToTree(treeInput);
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });
    const p = new TreeNode(pInput), q = new TreeNode(qInput);

    let current = root;

    while (current) {
        const vm = tree.makeVisManagerForNode(current);
        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔵 Visiting the ${makeColoredSpan('current node', CURRENT_COLOR)} with value <b>${current.val}</b>.  
            Compare this value with <b>p.val = ${p.val}</b> and <b>q.val = ${q.val}</b> to decide whether this node is the <b>Lowest Common Ancestor (LCA)</b>;  
            if not, use the <b>BST property</b> to choose the correct direction and continue the search.
        `);
        if (p.val < current.val && q.val < current.val) {
            notification(`
                ⬅️ Both target values are smaller than the value of the ${makeColoredSpan('current node', CURRENT_COLOR)}  
                (<b>${p.val}</b>, <b>${q.val}</b> < <b>${current.val}</b>).  
                In a BST, this guarantees the <b>Lowest Common Ancestor (LCA)</b> must lie in the <b>left subtree</b>.  
                Moving left.
            `);
            endBatch();
            current = current.left;
        } else if (p.val > current.val && q.val > current.val) {
            notification(`
                ⬅️ Both target values are larger than the value of the ${makeColoredSpan('current node', CURRENT_COLOR)}  
                (<b>${p.val}</b>, <b>${q.val}</b> > <b>${current.val}</b>).  
                In a BST, this guarantees the <b>Lowest Common Ancestor (LCA)</b> must lie in the <b>right subtree</b>.  
                Moving right.
            `);
            endBatch();
            current = current.right;
        } else {
            notification(`
                🎯 Split or match at the ${makeColoredSpan('current node', CURRENT_COLOR)} whose value is <b>${current.val}</b>.  
                The target values either fall on <b>different sides</b> of the ${makeColoredSpan('current node', CURRENT_COLOR)},  
                or the ${makeColoredSpan('current node', CURRENT_COLOR)} is one of them. <br>
                Therefore, the ${makeColoredSpan('current node', CURRENT_COLOR)} is the ${makeColoredSpan('Lowest Common Ancestor (LCA)', LCA_COLOR)}. <br>
                Returning the ${makeColoredSpan('current node', CURRENT_COLOR)} as the result.
            `);
            vm.addClass(LCA);
            endBatch();
            return current;
        }
    }
}

// --- Visual helpers ---

let currentNodeVM = null;

function setCurrentNode(vm) {
    if (currentNodeVM) currentNodeVM.removeClass(CURRENT);
    vm.addClass(CURRENT);
    currentNodeVM = vm; 
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(LCA, { backgroundColor: LCA_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    <b>🎨 Visual Cues (Color Schema)</b>
    <ul>
      <li>${makeColoredSpan('Current node', CURRENT_COLOR)} — ${CURRENT_COLOR} border while being visited and compared against <b>p.val</b> and <b>q.val</b>.</li>
      <li>${makeColoredSpan('LCA found', LCA_COLOR)} — ${LCA_COLOR} background for the node identified as the <b>Lowest Common Ancestor</b>.</li>
    </ul>
  `);
}

Approach

📌 Notes

p and q are present in the tree.
The tree is a BST with unique node values.
p ≠ q.

🧠 Main Idea

We exploit the BST property to find the Lowest Common Ancestor (LCA) by walking down from the root. At each step, let the currentNode have value currVal:

Both target values smaller: If p.val < currVal and q.val < currVal, the LCA must lie in the left subtree, so set currentNode = currentNode.left.
Both target values larger: If p.val > currVal and q.val > currVal, the LCA must lie in the right subtree, so set currentNode = currentNode.right.
Split or match: Otherwise (they are on different sides of currentNode or currentNode is one of them), currentNode is the LCA. Return it.

🧠 Correctness Intuition

In a BST where all values are unique, every value in the left subtree of a node is smaller than the node’s own value, and every value in the right subtree is larger. If both targets are on the same side, the current node cannot be their LCA (there exists a deeper common ancestor on that side), so we continue the search in that direction. The first node where either the paths to p and q diverge, or current node is one of them, is by definition their Lowest Common Ancestor.

Time Complexity

O(h), where h is the tree height — the longest possible path from the root down to the found LCA has a length of at most h − 1.

Space Complexity

O(1) auxiliary space is used — an iterative walk that employs only a few scalar variables, with no recursion or additional data structures.

Input-1

Lowest Common Ancestor of a Binary Search Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

📌 Notes

🧠 Main Idea

🧠 Correctness Intuition

Time Complexity

Space Complexity