DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Lowest Common Ancestor of a Binary Search Tree

Problem statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Problem statement taken from: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Example 1:

Container

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Container

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: root = [2, 1], p = 2, q = 1
Output: 2
Enter fullscreen mode Exit fullscreen mode

Constraints:

- The number of nodes in the tree is in the range [2, 10^5]
- -10^9 <= Node.val <= 10^9
- All Node.val are unique
- p != q
- p and q will exist in the BST
Enter fullscreen mode Exit fullscreen mode

Explanation

Storing paths

The solution in this approach is to store the path from the root to p and root to q in two separate arrays. We then find the first element in the arrays that are mismatched.

For Example 2:

The path from the root to 2: [6, 2]

The path from the root to 4: [6, 2, 4]

We find the first element: 6 matches. We check the next element, which is 2, and it matches. The array for path root to 2 is done, and the array for path root to 4 has an element at the 2nd index; we consider it a mismatch.

We return the last element in both the arrays that match, which is 2.

A C++ snippet of the above approach is as follows:

bool findPath(Node* root, vector<int>& path, int k) {
    if (root == NULL) {
        return false;
    }

    path.push_back(root->val);

    if (root->val == k) {
        return true;
    }

    if ((root->left && findPath(root->left, path, k))
        || (root->right && findPath(root->right, path, k))) {
        return true;
    }

    path.pop_back();
    return false;
}

int findLCA(Node* root, int p, int q) {
    vector<int> path1, path2;
    int i;

    if (!findPath(root, path1, p)
        || !findPath(root, path2, q)) {
        return -1;
    }

    for (i = 0; i < path1.size() && i < path2.size(); i++)
        if (path1[i] != path2[i])
            break;

    return path1[i - 1];
}
Enter fullscreen mode Exit fullscreen mode

The time complexity and the space complexity of the above approach is O(n).

Single Traversal

We use preorder traversal and solve the problem using below steps:

  • We check if the value of the root matches p and q
    • If yes, we return the root
    • else we recursively call the left and right subtree
  • If there is any root that returns one NULL and one NON-NULL value, we return the corresponding NON-NULL value for that node.
  • The root that returns both NON-NULL values for both the left and right subtree, is our LCA.

A C++ snippet of the above approach is as follows:

struct Node* findLCA(struct Node* root, int p, int q) {
    if (root == NULL)
        return NULL;

    if (root->key == p || root->key == q)
        return root;

    Node* leftLCA = findLCA(root->left, p, q);
    Node* rightLCA = findLCA(root->right, p, q);

    if (leftLCA && rightLCA) {
        return root;
    }

    return (leftLCA != NULL) ? leftLCA : rightLCA;
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(n), and the space complexity is O(h), where h is the tree's height.

Recursion

The problem statement states that the tree is a Binary Search Tree (BST). We can modify the above recursive approach to avoid unnecessary calls to the left and right subtree.

Let's check the algorithm first.

- if root == null
  - return null

- if root->val > p->val && root->val > q->val
  - return lca(root->left, p, q)

- if root->val < p->val && root->val < q->val
  - return lca(root->right, p, q)

- return root
Enter fullscreen mode Exit fullscreen mode

This approach's time and space complexity are O(h), where h is the tree's height.

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) {
            return NULL;
        }

        if(root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        }

        if(root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }

        return root;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    if root.Val > p.Val && root.Val > q.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }

    if root.Val < p.Val && root.Val < q.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }

    return root
}
Enter fullscreen mode Exit fullscreen mode

JavaScript solution

var lowestCommonAncestor = function(root, p, q) {
    if(root === null) {
        return null;
    }

    if(root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }

    if(root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }

    return root;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
       p = 2
       q = 4

Step 1: if root == NULL
          root -> 6
          false

        if root->val > p->val && root->val > q->val
          6 > 2 && 6 > 4
          true

          return lowestCommonAncestor(root->left, p, q)
               lowestCommonAncestor(->2, ->2, ->4)

// lowestCommonAncestor(->2, ->2, ->4)
Step 2: if root == NULL
          root -> 2
          false

        if root->val > p->val && root->val > q->val
          2 > 2 && 2 > 4
          false

        if root->val < p->val && root->val < q->val
          2 < 2 && 2 < 4
          false

        return root

        We backtrack to Step 1

Step 3: return lowestCommonAncestor(root->left, p, q)
               lowestCommonAncestor(->2, ->2, ->4)
               2

We return the answer as 2.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)