Question

Leetcode.235 Lowest Common Ancestor of a Binary Search Tree

Optimal Space & Time Complexity

- Time complexity: O()
- Space complexity: O()

Thoughts & Solutions

YC

Code

---

Sol

Code

var lowestCommonAncestor = function (root, p, q) {
    let cur = root;
    while (cur) {
        if (p.val < cur.val && q.val < cur.val) {
            cur = cur.left
        } else if (p.val > cur.val && q.val > cur.val) {
            cur = cur.right
        } else {
            return cur
        }
    }
};

---

東

Code

var lowestCommonAncestor = function(root, p, q) {
    // Time O(h) | Space O(1) 
    // h is the height of tree, which would be O(logN) if tree is balanced and O(N) if it is one sided tree;  
    let curr = root; 
    while(true) {
        if(curr.val > p.val && curr.val > q.val) {
            curr = curr.left;
        } else if (curr.val < p.val && curr.val < q.val) {
            curr = curr.right;
        } else {
            return curr;
        }
    }
};

Related Question
236. Lowest Common Ancestor of a Binary Tree

---

Jessie

Code

Excalidraw

//    BST 特性 left < current < right
//    MEMO: 我覺得這一題可以命名為 找兩個親戚之間輩份最大的交集
var lowestCommonAncestor = function (root, p, q) {

  while (root) {

    let keepSearching = false;

    if (p.val < root.val && q.val < root.val) {
      root = root.left;
      keepSearching = true;
    }

    if (p.val > root.val && q.val > root.val) {
      root = root.right;
      keepSearching = true;
    }

    if (!keepSearching) return root;

  }

};

---

皮皮

Code

---

Howard

Code

class Solution1:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # time O(N)
        # space O(N)
        
        bigger = p if p.val > q.val else q
        smaller = p if p.val < q.val else q

        if root.val > p.val and root.val > q.val:
            # go left
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            # go right
            return self.lowestCommonAncestor(root.right, p, q)
        elif smaller.val < root.val < bigger.val:
            # in between
            return root
        else:
            # reach q or p
            # note: 可以再把最後兩個 condition 變成一個 else，只是分開寫 case 更清楚
            return root
        
class Solution2:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 暴力解，沒有 node 大小條件也適用 (binary tree)
        #
        # time O(N)
        # space O(N)
        #
        # 1. find p and q path (from root)
        self.path = []
        self.p = p
        self.q = q
        self.p_path = None
        self.q_path = None
        
        self.find_path(root)

        # 2. compare the last node one by one
        common_last_index = min(len(self.p_path), len(self.q_path))
        for i in range(common_last_index-1, -1, -1):
            if self.p_path[i] == self.q_path[i]:
                return self.p_path[i]
    
    def find_path(self, current):
        # dfs
        # if find p or q, save the path in an array
        # 直覺上用 recursive 比較容易只有一個 variable 紀錄 path 現在走到哪一層
        if not current:
            return
        
        self.path.append(current)
        
        if current == self.p:
            self.p_path = self.path[:]
        if current == self.q:
            self.q_path = self.path[:]
        
        self.find_path(current.left)
        self.find_path(current.right)

        self.path.pop()

Live Coding

(name)

// write your code here