Tree Intro

What is a Tree

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

102. Binary Tree Level Order Traversal ::2:: - Medium

Topics: Tree, Breadth First Search, Binary Tree

Intro

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

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

Constraints:

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

-1000 ≤ Node.val ≤ 1000

Abstraction

Traverse a tree and return list of nodes grouped by level.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: BFS Iterative - Tree/DFS Pre order Traversal

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty check
        if not root:
            return []
        
        groups = []
        queue = deque([root])  # start with root
        
        while queue:
            # grab size of current level
            size = len(queue)
            level = []
            
            # process each node in this level
            for _ in range(size):
                node = queue.popleft()
                level.append(node.val)
                
                # enqueue children for next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            groups.append(level)
        
        return groups

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Recursive - Tree/DFS Pre order Traversal

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    append root to corresponding depth group
        # 2. Process -> left -> right :
        # Results: nodes grouped by depth level
        
        # depth level groups
        groups = []
        
        def dfs(node, depth):

            # Empty check
            if not node:
                return
            
            # Process root -> :
            # add group if new depth reached
            if len(groups) == depth:
                groups.append([])
            
            # Process root -> : 
            # add node to corresponding depth group
            groups[depth].append(node.val)
            
            # Process -> left -> right : update depth
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        dfs(root, 0)

        # overall: time complexity
        # overall: space complexity
        return groups

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

199. Binary Tree Right Side View ::2:: - Medium

Topics: Tree, Breadth First Search, Binary Tree

Intro

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example Input	Output
root = [1,2,3,null,5,null,4]	[1,3,4]
root = [1,2,3,4,null,null,null,5]	[1,3,4,5]
root = [1,null,3]	[1,3]
root = []	[]

Constraints:

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

-100 ≤ Node.val ≤ 100

Abstraction

Given a tree, if you were to stand on the right side, return all nodes that you would have a direct line of sight to (not hidden by right-er nodes)

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: BFS Pre Order Iterative Grab Last Element Per Level - Tree/DFS Pre order Traversal

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # BFS pre order: process level : root -> left -> right
        # 1. For each level
        # 2. Process root -> :
        #    grab length of level, if root is last element in group, add to res
        # 3. Process -> left -> right :
        # Result: right most element of each level added
        
        # Empty check
        if not root:
            return []
        
        # right most elements of each level
        result = []
        
        # iterative queue
        queue = deque([root])
        
        while queue:

            # process entire level
            level_size = len(queue)
            for i in range(level_size):

                # Process root -> : 
                node = queue.popleft()

                # Process root -> : 
                # if this is last element in level, add to res
                if i == level_size - 1:
                    result.append(node.val)

                # Process -> left -> right : 
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Recursive Right Subtree Search With New Depth Trigger - Tree/DFS Pre order Traversal

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # DFS pre order: root -> right -> left
        # 1. Process root -> : 
        # 2. Process -> right -> left
        #    we are exploring right subtree first,
        #    first time we hit a new depth, we must be at right most node,
        #    add node to res
        # Result: right most element of each level added

        # right most elements of each level
        result = []
        
        def dfs(node, depth):

            # Empty check
            if not node:
                return

            # Process root -> :
            # if hit new depth, must be at right most node
            if depth == len(result):
                result.append(node.val)

            # Process -> right -> left
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        # recursive call on root
        dfs(root, 0)

        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

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 I BFS