Definition for a binary tree node.

Solved at: 220925. Took 17m 09s

Question

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

According to thedefinition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodespandqas the lowest node inTthat has bothpandqas descendants (where we allowa node to be a descendant of itself)."

Solution

python

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

I misunderstood LCA as being the minimum in value.

Results

Runtime

89 ms, faster than 86.27% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Memory Usage

18.9 MB, less than 23.33% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Improvements

I ignored that this is a Binary Search Tree, not just Binary Tree. Therefore one can binary search to reduce the search scope.

Complexity Analysis

For this, It will be $O(N)$ where $N$ is the count of the nodes. Space complexity will be $O(N)$ for constructing lists and dictionaries.

If we use the above improvement, space complexity will reduce to $O(1)$ . However, time complexity will not change.

Backlinks (2)

컴퓨트로늄

컴퓨트로늄 정의

컴퓨트로늄이 뭐야?

컴퓨트로늄(computronium)은 계산을 수행하는 데 최적으로 설계된 가상의 물질이다.

쉽게 말하면, “물질을 최대한 컴퓨터처럼 만든 것”이다. 일반 컴퓨터는 실리콘 칩, 전선, 냉각 장치, 케이스처럼 계산에 직접 쓰이지 않는 부분이 많다. 컴퓨트로늄은 그런 낭비를 극단적으로 줄이고, 물질의 질량·에너지·구조 전체를 계산에 쓰도록 만든다는 개념이다.

예시로는 다음이 있다.

행성 전체를 컴퓨터로 바꾼 구조
별의 에너지를 둘러싸서 계산에 쓰는 거대 컴퓨터
인간 뇌보다 훨씬 조밀한 인공 신경망 물질
우주 전체를 계산 장치처럼 재구성한다는 극단적 미래 시나리오

이 개념은 주로 SF, 미래학, 인공지능 이론, 트랜스휴머니즘, 우주공학적 상상에서 나온다.

핵심은 이것이다.

컴퓨트로늄 = 계산 효율을 극한까지 높이기 위해 재구성된 물질

현실에 아직 존재하는 물질 이름은 아니다. 물리학적으로 가능한 한계, 열 방출, 에너지 공급, 정보 저장 밀도 같은 제약 때문에 실제 구현은 가설 수준이다.

Backlinks (2)

Definition for a binary tree node.

Warning

This post is more than a year old. Information may be outdated.

Solved at: 220925. Took 17m 09s

Question

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

Solution

python

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        found_p = False        found_q = False
        queue = [root]
        ancestor = {}
        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)
        current = p        p_path = [current]
        while current != root:            current = ancestor[current]            p_path.append(current)
        current = q        q_path = [current]
        while current != root:            current = ancestor[current]            q_path.append(current)
        lca = root
        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")
        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break
        return lca

I misunderstood LCA as being the minimum in value.

Results

Runtime

89 ms, faster than 86.27% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Memory Usage

18.9 MB, less than 23.33% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

Improvements

I ignored that this is a Binary Search Tree, not just Binary Tree. Therefore one can binary search to reduce the search scope.

Complexity Analysis

For this, It will be $O(N)$ where $N$ is the count of the nodes. Space complexity will be $O(N)$ for constructing lists and dictionaries.

If we use the above improvement, space complexity will reduce to $O(1)$ . However, time complexity will not change.

Backlinks (2)

컴퓨트로늄

260419

Definition for a binary tree node.

Question

Solution

Results

Runtime

Memory Usage

Improvements

Complexity Analysis

컴퓨트로늄

260419

Definition for a binary tree node.

Question

Solution

Results

Runtime

Memory Usage

Improvements

Complexity Analysis