leetcode/javascript/235-lowest-common-ancestor-of-a-binary-search-tree.js at main · remenraj/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 * Time O(N) | Space O(H)
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
    const isGreater = (p.val < root.val) && (q.val < root.val);
    if (isGreater) return lowestCommonAncestor(root.left, p, q);

    const isLess = (root.val < p.val) && (root.val < q.val);
    if (isLess) return lowestCommonAncestor(root.right, p, q);

    return root;
};

/**
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 * Time O(N) | Space O(1)
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
    while (root !== null) {
        const isGreater = (root.val < p.val) && (root.val < q.val)
        if (isGreater) {
            root = root.right;
            continue;
        }

        const isLess = (p.val < root.val) && (q.val < root.val);;
        if (isLess) {
            root = root.left;
            continue;
        }

        break;
    }

    return root;
};