JSFiddle - React, Tailwind, and code Playground

by mickeyvip

HTML

<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/jasmine/2.0.0/jasmine.css">
<script src="//cdnjs.cloudflare.com/ajax/libs/jasmine/2.0.0/jasmine.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/jasmine/2.0.0/jasmine-html.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/jasmine/2.0.0/boot.js"></script>

JavaScript

/*
    Lowest Common Ancestor finder
    Assumes that both nodes are present in the tree with root "root"
    
*/
function lca(root, a, b) {
    if (root === a || root === b || root === null) {
        return root;
    }

    var left = lca(root.left, a, b);
    var right = lca(root.right, a, b);

    return left && right ? root : left || right;
}

function findNode(root, nodeValue) {
    if (root === null || root.value === nodeValue) {
        return root;
    } else {
        var left = findNode(root.left, nodeValue);
        if (left) {
            return left;
        }
        var right = findNode(root.right, nodeValue);
        if (right) {
            return right;
        }
    }
    return null;
};

describe("findNode", function () {
    it("should be able to find a node by value", function () {
        var tree1 = {
            value: "root",
            left: {
                value: "a",
                left: null,
                right: null
            },
            right: {
                value: "b",
                left: null,
                right: null
            }
        };
        var root = findNode(tree1, "root");
        var a = findNode(tree1, "a");
        var b = findNode(tree1, "b");

        expect(root).toEqual(tree1);
        expect(a).toEqual(tree1.left);
        expect(b).toEqual(tree1.right);
    });
});

describe("lca", function () {
    it("should return root if there is only a and b in the tree under root", function () {
        var tree = {
            value: "root",
            left: {
                value: "a",
                left: null,
                right: null
            },
            right: {
                value: "b",
                left: null,
                right: null
            }
        };
        var a = findNode(tree, "a");
        var b = findNode(tree, "b");

        expect(lca(tree, a, b)).toEqual(tree);
    });

    it("should return parent node p of a and b if a and b are immideate children of...