Tree Reroot Intro

What is a Tree

Trees are hierarchical data structures representing relationships between entities, often in a parent-child format.

834. Sum of Distances in Tree ::1:: - Hard

Topics: Dynamic Programming, Tree, Depth First Search, Graph Theory

Intro

There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.

Example Input	Output
n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]	[8,12,6,10,10,10]
n = 1, edges = []	[0]
n = 2, edges = [[1,0]]	[1,1]

Constraints:

1 ≤ n ≤ 3 * 10^4

edges.length == n - 1

edges[i].length == 2

0 ≤ ai, bi < n

ai != bi

The given input represents a valid tree

Abstraction

something!

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [DFS] Re Rooting DP On Trees - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        
        # Build tree adjacency list
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)

        res = [0] * n        # result: sum of distances for each node
        count = [1] * n      # subtree sizes (initialize to 1 for self)

        # Post-order DFS:
        def dfs1(node, parent):
            for child in tree[node]:
                if child == parent:
                    continue
                dfs1(child, node)
                count[node] += count[child]
                res[node] += res[child] + count[child]

        # Pre-order DFS:
        def dfs2(node, parent):
            for child in tree[node]:
                if child == parent:
                    continue
                # Shift root from node -> child
                res[child] = res[node] - count[child] + (n - count[child])
                dfs2(child, node)

        dfs1(0, -1)  # post-order: compute subtree sizes and partial sums
        dfs2(0, -1)  # pre-order: propagate distances to children

        return res

987. Vertical Order Traversal of a Binary Tree ::1:: - Hard

Topics: Hash Table, Tree, Depth First Search, Breath First Search, Sorting, Binary Tree

Intro

Given the root of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0) The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the vertical order traversal of the binary tree.

Example Input	Output
root = [3,9,20,null,null,15,7]	[[9],[3,15],[20],[7]]
root = [1,2,3,4,5,6,7]	[[4],[2],[1,5,6],[3],[7]]
root = [1,2,3,4,6,5,7]	[[4],[2],[1,5,6],[3],[7]]

Constraints:

The number of nodes in the tree is in the range [1, 1000].

0 ≤ Node.val ≤ 1000

Abstraction

something!

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [DFS] Re Rooting DP On Trees - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:

        # DFS + Coordinate Tracking + Sorting
        
        # Idea:
        #   - Each node has coordinates (row, col)
        #   - Left child  -> (row + 1, col - 1)
        #   - Right child -> (row + 1, col + 1)
        #   - Store all nodes as (col, row, value)
        #   - Sort to satisfy vertical traversal ordering.
        
        # Rules:
        #   1. DFS traversal assigning coordinates.
        #   2. Sort by column, row, value.
        #   3. Group nodes by column.
        
        # Complexity:
        #   - Time: O(n log n)   (sorting)
        #   - Space: O(n)

        nodes = []  # (col, row, value)

        # DFS traversal
        def dfs(node, row, col):
            if not node:
                return

            nodes.append((col, row, node.val))

            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        # Sort by col -> row -> value
        nodes.sort()

        # Group by column
        res = []
        prev_col = float('-inf')

        for col, row, val in nodes:
            if col != prev_col:
                res.append([])
                prev_col = col
            res[-1].append(val)

        return res

669. Trim a Binary Search Tree ::1:: - Medium

Topics: Dynamic Programming, Tree, Depth First Search, Graph Theory

Intro

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example Input	Output
root = [1,0,2], low = 1, high = 2	[1,null,2]
root = [3,0,4,null,2,null,null,1], low = 1, high = 3	[3,2,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 10^4]

0 ≤ Node.val ≤ 10^4

The value of each node in the tree is unique

root is guaranteed to be a valid binary search tree

0 ≤ low ≤ high ≤ 10^4

Abstraction

something!

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [DFS] DFS And BFS Pruning Optimization - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        # DFS + BST Optimization
        #
        # Idea:
        #   - Use BST property to prune entire subtrees.
        #
        # Rules:
        #   1. If node.val < low:
        #        - left subtree is invalid
        #        - return trimmed right subtree
        #
        #   2. If node.val > high:
        #        - right subtree is invalid
        #        - return trimmed left subtree
         
        #   3. Otherwise:
        #        - node is valid
        #        - recursively trim both children
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(h) (recursion stack)

        if not root:
            return None

        # Node too small → discard left side
        if root.val < low:
            return self.trimBST(root.right, low, high)

        # Node too large → discard right side
        if root.val > high:
            return self.trimBST(root.left, low, high)

        # Node is valid → trim children
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        return root

2872. Maximum Number of K-Divisible Components ::1:: - Hard

Topics: Tree, Depth First Search

Intro

There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the ith node, and an integer k. A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by k, where the value of a connected component is the sum of the values of its nodes. Return the maximum number of components in any valid split.

Example Input	Output
n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6	2
n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3	3

Constraints:

1 ≤ n ≤ 3 * 10^4

edges.length == n - 1

edges[i].length == 2

0 ≤ ai, bi < n

values.length == n

0 ≤ values[i] ≤ 10^9

1 ≤ k ≤ 10^9

Sum of values is divisible by k

The input is generated such that edges represents a valid tree

Abstraction

something!

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [DFS] DFS And BFS Pruning Optimization - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        # DFS + Greedy Tree Cutting
        #
        # Idea:
        #   - Post-order DFS computes subtree sums.
        #   - If subtree sum % k == 0:
        #         -> count one component
        #         -> return 0 to parent (cut edge)
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

        # ----------------------
        # Build adjacency list
        # ----------------------
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        components = 0

        # ----------------------
        # Post-order DFS
        # ----------------------
        def dfs(node, parent):
            nonlocal components

            subtree_sum = values[node]

            for nei in graph[node]:
                if nei == parent:
                    continue

                subtree_sum += dfs(nei, node)

            # If divisible -> create component
            if subtree_sum % k == 0:
                components += 1
                return 0   # cut here

            return subtree_sum

        dfs(0, -1)

        return components

LeetCode: Trees II DFS