Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode Road] Lowest Common Ancestor of a Binary Search Tree - Solution/C++

Posted on Edited on In Disqus:

235. Lowest Common Ancestor of a Binary Search Tree

Question:

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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).”

Example:

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.

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.

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:
  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

    • Source code

    Version 1

    Idea:
    Let's talk about the BST features:
    1) All values of the left node as the root's sub-tree are smaller than root value,
    2) All values of the right node as the root's sub-tree are bigger than root,
    3) Any nodes's left/right sub-tree are match to BST principle,
    4) No exists the same key-value of node.

    So, use the BST principle we can compare the current node's value with left/right child, and find the answer.

    Time complexity: O(n)
    Space complexity: O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if((p->val < root->val) && (q->val < root->val)){
                return lowestCommonAncestor(root->left, p, q);
            }
            
            if((p->val > root->val) && (q->val > root->val)){
                return lowestCommonAncestor(root->right, p, q);
            }
            
            return root;  
        }
    };

    Version 2

    Idea:
    This is an iterator method.

    Time complexity: O(n)
    Space complexity: O(1)

    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
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            while(true){
                if(root->val > p->val && root->val > q->val){
                    root = root->left;
                }else if(root->val < p->val && root->val < q->val){
                    root = root->right;
                }else{
                    break;
                }
            }
            return root;
        }
    };