LeetCode: Trees

Intro

Trees are hierachical data structures representing relationships between entities, often in a parent-child format. Trees are a special type of graph, characters by:

Nodes: The entities (ex: values, objects)
Edges: The connections between the entities. A tree with n nodes has n - 1 edges.
Root: The top-most node, with no parent
Leaves: Nodes with no children
Height: The number of edges on the longest path from the root to a leaf
Depth: The number of edges from the root to a specific node
Cycles: Trees do not contain cycles
Paths: Trees have exactly one path between any two nodes

Tree:

Parent Array:

Index (Node):   1   2   3   4   5
Parent:        N/A  1   1   3   3

Tree Representations

Please see graph representations

Tree Application: MinHeap

Use a MinHeap, a type of binary tree, to maintain the smallest or highest-priority elements efficiently.

Ex: Find the Top K Frequent Elements in a List

    def topKFrequent(nums: List[int], k: int) -> List[int]:
        from collections import defaultdict
        import heapq

        # Step 1: Frequency count for each unique integer
        count = defaultdict(int)  # O(m) space complexity for m unique integers
        for num in nums:  # O(n) time complexity to iterate over n integers
            count[num] += 1

        # Step 2: Use a MinHeap to track the k most frequent elements
        minHeap = []  # O(k) space complexity for k elements
        for num, freq in count.items():  # O(m) time complexity for m unique integers
            heapq.heappush(minHeap, (freq, num))  # O(log k) for each insertion
            if len(minHeap) > k:  # Ensure heap size remains k
                heapq.heappop(minHeap)  # O(log k) for each removal

        # Step 3: Extract the elements from the heap
        return [num for freq, num in minHeap]  # O(k) time complexity to extract results

    # Example:
    # Input: nums = [1, 1, 1, 2, 2, 3], k = 2
    # Output: [1, 2]