Tree Reroot Intro

What is a Tree

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

103. Binary Tree Zigzag Level Order Traversal ::1:: - Medium

Topics: Tree, Breadth First Search, Binary Tree

Intro

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example Input	Output
root = [3,9,20,null,null,15,7]	[[3],[20,9],[15,7]]
root = [1]	[[1]]
root = []	[]

Constraints:

The number of nodes in the tree is in the range [0, 2000].

-100 ≤ Node.val ≤ 100

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: [BFS] BFS And BFS Pruning Optimization - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # BFS Level Order + Zigzag
        
        # Idea:
        #   - Standard BFS level traversal.
        #   - Use deque for current level:
        #       left->right  : append()
        #       right->left  : appendleft()
        #   - Toggle direction after each level.
        
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

        if not root:
            return []

        queue = deque([root])
        res = []
        left_to_right = True

        while queue:

            level_size = len(queue)
            level = deque()   # allows O(1) insertion both ends

            for _ in range(level_size):
                node = queue.popleft()

                # Zigzag insertion
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)

                # Normal BFS expansion
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            res.append(list(level))

            # flip direction
            left_to_right = not left_to_right

        return res

1765. Map of Highest Peak ::1:: - Medium

Topics: Array, Breadth First Search, Matrix

Intro

You are given an integer matrix isWater of size m x n that represents a map of land and water cells. If isWater[i][j] == 0, cell (i, j) is a land cell. If isWater[i][j] == 1, cell (i, j) is a water cell. You must assign each cell a height in a way that follows these rules: The height of each cell must be non-negative. If the cell is a water cell, its height must be 0. Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching). Find an assignment of heights such that the maximum height in the matrix is maximized. Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

Example Input	Output
isWater = [[0,1],[0,0]]	[[1,0],[2,1]]
isWater = [[0,0,1],[1,0,0],[0,0,0]]	[[1,1,0],[0,1,1],[1,2,2]]

Constraints:

m == isWater.length

n == isWater[i].length

1 ≤ m, n ≤ 1000

isWater[i][j] is 0 or 1

There is at least one water cell

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 highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        # Dimensions
        m, n = len(isWater), len(isWater[0])

        # Initialize height grid with -1 (unvisited)
        height = [[-1] * n for _ in range(m)]

        # BFS queue: start with all water cells
        queue = deque()
        for r in range(m):
            for c in range(n):
                if isWater[r][c] == 1:
                    height[r][c] = 0
                    queue.append((r, c))

        # Directions: up, down, left, right
        directions = [(1,0), (-1,0), (0,1), (0,-1)]

        # BFS: propagate heights
        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Early pruning: skip out-of-bounds or already visited
                if 0 <= nr < m and 0 <= nc < n and height[nr][nc] == -1:
                    height[nr][nc] = height[r][c] + 1
                    queue.append((nr, nc))

        return height

LeetCode: Trees II BFS