Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 222: Count Complete Tree Nodes — Python Solution

    Solve LeetCode 222: Count Complete Tree Nodes in Python with a perfect-subtree detection approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternperfect-subtree detection
    ComplexityO(log^2 n) time and O(log n) recursion space

    What the problem is testing

    Compare leftmost and rightmost heights. Equal heights identify a perfect subtree whose size is computed directly; otherwise recurse.

    Algorithm

    1. Compare leftmost and rightmost heights. Equal heights identify a perfect subtree whose size is computed directly; otherwise recurse.
    2. Maintain this invariant: Equal extreme heights in a complete subtree imply every level is full.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def countNodes(self, root):
        def left_height(node):
            height = 0
            while node: height += 1; node = node.left
            return height
        def right_height(node):
            height = 0
            while node: height += 1; node = node.right
            return height
        if not root:
            return 0
        left, right = left_height(root), right_height(root)
        if left == right:
            return (1 << left) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    Why this is correct

    The proof follows the maintained state: Equal extreme heights in a complete subtree imply every level is full. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(log^2 n) time and O(log n) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    An empty subtree has size zero; height counts must use the same convention.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 173. Binary Search Tree Iterator · Next: 236. Lowest Common Ancestor of a Binary Tree

  • LeetCode 236: Lowest Common Ancestor of a Binary Tree — Python Solution

    Solve LeetCode 236: Lowest Common Ancestor of a Binary Tree in Python with a postorder target propagation approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternpostorder target propagation
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Return a node when it is a target or when targets are found in both child subtrees; otherwise propagate the one non-null result.

    Algorithm

    1. Return a node when it is a target or when targets are found in both child subtrees; otherwise propagate the one non-null result.
    2. Maintain this invariant: A non-null return means that subtree contains at least one target, and the first node receiving two results is their lowest common ancestor.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

    Why this is correct

    The proof follows the maintained state: A non-null return means that subtree contains at least one target, and the first node receiving two results is their lowest common ancestor. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(h) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    One target may be an ancestor of the other.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 222. Count Complete Tree Nodes · Next: 199. Binary Tree Right Side View

  • LeetCode 199: Binary Tree Right Side View — Python Solution

    Solve LeetCode 199: Binary Tree Right Side View in Python with a level-order last node approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree BFS
    Reusable patternlevel-order last node
    ComplexityO(n) time and O(w) space

    What the problem is testing

    Process the tree level by level and record the value of the final node dequeued from each level.

    Algorithm

    1. Process the tree level by level and record the value of the final node dequeued from each level.
    2. Maintain this invariant: The queue segment for a level is ordered left-to-right, so its final node is visible from the right.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def rightSideView(self, root):
        if not root:
            return []
        queue, answer = deque([root]), []
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            answer.append(node.val)
        return answer

    Why this is correct

    The proof follows the maintained state: The queue segment for a level is ordered left-to-right, so its final node is visible from the right. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(w) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    An empty tree produces an empty list.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 236. Lowest Common Ancestor of a Binary Tree · Next: 637. Average of Levels in Binary Tree

  • LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal — Python Solution

    Solve LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal in Python with a reverse postorder partition approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternreverse postorder partition
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Take roots from postorder backward and build the right subtree before the left using inorder boundaries.

    Algorithm

    1. Take roots from postorder backward and build the right subtree before the left using inorder boundaries.
    2. Maintain this invariant: The reverse postorder cursor identifies the root of the current inorder range, followed by its right subtree.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def buildTree(self, inorder, postorder):
        position = {value: i for i, value in enumerate(inorder)}
        post_index = len(postorder) - 1
        def build(left, right):
            nonlocal post_index
            if left > right:
                return None
            value = postorder[post_index]
            post_index -= 1
            root = TreeNode(value)
            split = position[value]
            root.right = build(split + 1, right)
            root.left = build(left, split - 1)
            return root
        return build(0, len(inorder) - 1)

    Why this is correct

    The proof follows the maintained state: The reverse postorder cursor identifies the root of the current inorder range, followed by its right subtree. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Building left first would consume roots in the wrong order.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 105. Construct Binary Tree from Preorder and Inorder Traversal · Next: 117. Populating Next Right Pointers in Each Node II

  • LeetCode 117: Populating Next Right Pointers in Each Node II — Python Solution

    Solve LeetCode 117: Populating Next Right Pointers in Each Node II in Python with a level linked-list construction approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternlevel linked-list construction
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Use the current level’s next pointers to scan horizontally while a dummy tail builds the next level’s next chain.

    Algorithm

    1. Use the current level’s next pointers to scan horizontally while a dummy tail builds the next level’s next chain.
    2. Maintain this invariant: The dummy chain contains every discovered child on the next level in left-to-right order.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def connect(self, root):
        current = root
        while current:
            dummy = tail = Node(0)
            while current:
                if current.left:
                    tail.next = current.left; tail = tail.next
                if current.right:
                    tail.next = current.right; tail = tail.next
                current = current.next
            current = dummy.next
        return root

    Why this is correct

    The proof follows the maintained state: The dummy chain contains every discovered child on the next level in left-to-right order. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(1) extra space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Sparse levels and missing left or right children require independent child checks.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 106. Construct Binary Tree from Inorder and Postorder Traversal · Next: 114. Flatten Binary Tree to Linked List

  • LeetCode 114: Flatten Binary Tree to Linked List — Python Solution

    Solve LeetCode 114: Flatten Binary Tree to Linked List in Python with a reverse preorder threading approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternreverse preorder threading
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Traverse right then left while keeping the previously processed node, and make each node point right to that previous node with left cleared.

    Algorithm

    1. Traverse right then left while keeping the previously processed node, and make each node point right to that previous node with left cleared.
    2. Maintain this invariant: prev is the already flattened successor sequence for the current node in preorder.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def flatten(self, root):
        previous = None
        def visit(node):
            nonlocal previous
            if not node:
                return
            visit(node.right)
            visit(node.left)
            node.right = previous
            node.left = None
            previous = node
        visit(root)

    Why this is correct

    The proof follows the maintained state: prev is the already flattened successor sequence for the current node in preorder. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(h) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Every left pointer must finish null.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 117. Populating Next Right Pointers in Each Node II · Next: 112. Path Sum

  • LeetCode 112: Path Sum — Python Solution

    Solve LeetCode 112: Path Sum in Python with a remaining-sum DFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyEasy
    TopicBinary Tree General
    Reusable patternremaining-sum DFS
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Subtract each node value and accept only when a leaf makes the remaining target exactly zero.

    Algorithm

    1. Subtract each node value and accept only when a leaf makes the remaining target exactly zero.
    2. Maintain this invariant: The remaining value equals the target minus the sum along the current root-to-node path.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        remaining = targetSum - root.val
        if not root.left and not root.right:
            return remaining == 0
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

    Why this is correct

    The proof follows the maintained state: The remaining value equals the target minus the sum along the current root-to-node path. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(h) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    A matching internal node is not enough; the path must end at a leaf.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 114. Flatten Binary Tree to Linked List · Next: 129. Sum Root to Leaf Numbers

  • LeetCode 129: Sum Root to Leaf Numbers — Python Solution

    Solve LeetCode 129: Sum Root to Leaf Numbers in Python with a prefix-number DFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternprefix-number DFS
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Extend the current number by multiplying by ten and adding the node digit; return it at leaves and sum child results.

    Algorithm

    1. Extend the current number by multiplying by ten and adding the node digit; return it at leaves and sum child results.
    2. Maintain this invariant: The accumulator is exactly the decimal number represented by the current root-to-node path.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def sumNumbers(self, root):
        def visit(node, prefix):
            if not node:
                return 0
            value = prefix * 10 + node.val
            if not node.left and not node.right:
                return value
            return visit(node.left, value) + visit(node.right, value)
        return visit(root, 0)

    Why this is correct

    The proof follows the maintained state: The accumulator is exactly the decimal number represented by the current root-to-node path. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(h) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    A zero digit still shifts the prefix; an empty tree contributes zero.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 112. Path Sum · Next: 124. Binary Tree Maximum Path Sum

  • LeetCode 146: LRU Cache — Python Solution

    Solve LeetCode 146: LRU Cache in Python with a hash map plus doubly linked list approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyMedium
    TopicLinked List
    Reusable patternhash map plus doubly linked list
    ComplexityO(1) average time per operation and O(capacity) space

    What the problem is testing

    Map keys to nodes and maintain recency in a doubly linked list. Reads and writes move a node to the most-recent end; overflow evicts the least-recent node.

    Algorithm

    1. Map keys to nodes and maintain recency in a doubly linked list. Reads and writes move a node to the most-recent end; overflow evicts the least-recent node.
    2. Maintain this invariant: List order is exact recency order and the map contains exactly the linked data nodes.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

    Why this is correct

    The proof follows the maintained state: List order is exact recency order and the map contains exactly the linked data nodes. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(1) average time per operation and O(capacity) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    Updating an existing key also refreshes it; capacity can be one.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 86. Partition List · Next: 104. Maximum Depth of Binary Tree

  • LeetCode 104: Maximum Depth of Binary Tree — Python Solution

    Solve LeetCode 104: Maximum Depth of Binary Tree in Python with a recursive postorder approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

    This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

    DifficultyEasy
    TopicBinary Tree General
    Reusable patternrecursive postorder
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    The depth of a node is one plus the larger depth of its children, with an empty subtree contributing zero.

    Algorithm

    1. The depth of a node is one plus the larger depth of its children, with an empty subtree contributing zero.
    2. Maintain this invariant: Each return value is the exact maximum root-to-leaf node count for that subtree.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

    LeetCode provides the list, tree, or graph node definition used by the method.

    from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

    Why this is correct

    The proof follows the maintained state: Each return value is the exact maximum root-to-leaf node count for that subtree. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

    O(n) time and O(h) recursion space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

    Edge cases

    An empty tree has depth zero; a skewed tree uses linear recursion depth.

    Tested reference code

    This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 146. LRU Cache · Next: 100. Same Tree