Skip to content

Instantly share code, notes, and snippets.

@jchiatt

jchiatt/lca.js

Created September 23, 2020 23:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jchiatt/5e4c93c3b01bb5722873e6084c4ee1c1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jchiatt/5e4c93c3b01bb5722873e6084c4ee1c1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jchiatt created this gist Sep 23, 2020.
    97 changes: 97 additions & 0 deletions lca.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,97 @@
    const root = {
    "id": 0,
    "children": [
    {
    "id": 1,
    "children": [
    {
    "id": 3,
    "children": [
    {
    "id": 7,
    "children": []
    },
    {
    "id": 8,
    "children": []
    }
    ]
    },
    {
    "id": 4,
    "children": [
    {
    "id": 9,
    "children": []
    },
    {
    "id": 10,
    "children": []
    }
    ]
    }
    ]
    },
    {
    "id": 2,
    "children": [
    {
    "id": 5,
    "children": [
    {
    "id": 11,
    "children": []
    },
    {
    "id": 12,
    "children": []
    }
    ]
    },
    {
    "id": 6,
    "children": [
    {
    "id": 13,
    "children": []
    },
    {
    "id": 14,
    "children": []
    }
    ]
    }
    ]
    }
    ]
    }

    // write a function getLowestCommonAncestor(root, id1, id2)
    // it should return the lowest common ancestor
    // getLowestCommonAncestor(root, 13, 13) === 13
    // getLowestCommonAncestor(root, 14, 14) === 14
    // getLowestCommonAncestor(root, 13, 14) === 6
    // getLowestCommonAncestor(root, 12, 14) === 2
    // getLowestCommonAncestor(root, 7, 14) === 0

    function getLowestCommonAncestor(root, id1, id2) {
    const { id, children } = root;
    const isLeaf = children.length === 0;

    // node doesn't have a value
    if ( id === null ) return null;

    // node is a leaf and doesn't match
    if ( isLeaf && id !== id1 && id !== id2 ) return null;

    // node matches
    if ( id === id1 || id === id2 ) return id;

    const leftNode = getLowestCommonAncestor(children[0], id1, id2);
    const rightNode = getLowestCommonAncestor(children[1], id1, id2);

    if ( leftNode && rightNode ) return id;
    if ( !leftNode && !rightNode ) return null;

    return leftNode ? leftNode : rightNode;
    }