Inverting a Binary Tree

This problem requires mirroring the binary tree structure so that the left child becomes the right child and vice versa. A depth-first search (DFS) approach is suitable here, utilizing either pre-order or post-order traversal. The logic involves swapping the left and right pointers of the current node and then recursively processing the subtrees.

class Solution:
    def mirror_tree(self, node: TreeNode) -> TreeNode:
        if not node:
            return None
        
        # Swap the children
        node.left, node.right = node.right, node.left
        
        # Recursively mirror the subtrees
        self.mirror_tree(node.left)
        self.mirror_tree(node.right)
        
        return node

Symmetric Tree Verification

To determine if a tree is symmetric, we need to compare the left subtree with the right subtree. This is fundamentally a comparison of the outer nodes (left-left vs right-right) and the inner nodes (left-right vs right-left). Post-order traversal is effective here as we rely on the return values of the recursive calls to validate the symmetry at each level.

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.check_mirror(root.left, root.right)
    
    def check_mirror(self, left_node, right_node):
        # Handle None cases
        if left_node is None and right_node is not None: return False
        if left_node is not None and right_node is None: return False
        if left_node is None and right_node is None: return True
        
        # Check value mismatch
        if left_node.val != right_node.val:
            return False
        
        # Recursive check for outer and inner pairs
        outer_match = self.check_mirror(left_node.left, right_node.right)
        inner_match = self.check_mirror(left_node.right, right_node.left)
        
        return outer_match and inner_match

Maximum Depth of Binary Tree

The depth is calculated as the number of nodes along the longest path from the root to the furthest leaf. A post-order traversal (bottom-up) is the most efficient approach. We recursively compute the height of the left and right subtrees and return the maximum of the two plus one for the current node.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        left_h = self.maxDepth(root.left)
        right_h = self.maxDepth(root.right)
        
        return 1 + max(left_h, right_h)

Minimum Depth of Binary Tree

Finding the minimum depth requires care. It is defined as the number of nodes along the shortest path to a leaf node. A common mistake is to simply take the minimum of left and right depths. However, if a node has only one child, we must traverse down the side that has the child, as the node itself is not a leaf. Post-order traversal handles this logic effectively.

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        return self.calculate_depth(root)
        
    def calculate_depth(self, node):
        if not node:
            return 0
        
        left_d = self.calculate_depth(node.left)
        right_d = self.calculate_depth(node.right)
        
        # If one child is missing, we go down the existing side
        if node.left is None and node.right is not None:
            return 1 + right_d
        if node.left is not None and node.right is None:
            return 1 + left_d
        
        # If both children exist, take the minimum
        return 1 + min(left_d, right_d)

Counting Nodes in a Complete Binary Tree

A complete binary tree fills all levels except possibly the last, which is filled from left to right. We can optimize the counting by checking if the tree is a "perfect" binary tree (all levels filled). If the depth of the leftmost path equals the depth of the rightmost path, the tree is perfect, and the node count is $2^h - 1$. Otherwise, we recursively count the left and right subtrees.

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        left_node = root.left
        right_node = root.right
        left_depth = 0
        right_depth = 0
        
        while left_node:
            left_node = left_node.left
            left_depth += 1
        while right_node:
            right_node = right_node.right
            right_depth += 1
            
        # If it's a perfect binary tree
        if left_depth == right_depth:
            return (2 << left_depth) - 1
            
        # Otherwise, recurse normally
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Checking for a Balanced Binary Tree

A height-balanced binary tree is one where the depth of the two subtrees of every node never differs by more than one. We use a post-order traversal to calculate the height of each node. If we find a subtree that is already unbalanced, we propagate a failure signal (e.g., -1) up the recursion stack immediately.

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.check_height(root) != -1
    
    def check_height(self, node):
        if not node:
            return 0
        
        left_h = self.check_height(node.left)
        if left_h == -1: return -1
        
        right_h = self.check_height(node.right)
        if right_h == -1: return -1
        
        if abs(left_h - right_h) > 1:
            return -1
        
        return 1 + max(left_h, right_h)

Binary Tree Paths

This problem requires recording all paths from the root to leaf nodes. A pre-order traversal (DFS) is used here. We maintain a current path list. When we reach a leaf node, we convert the path list to a string and add it to our results. Backtracking is crucial: after processing a child node, we must remove it from the current path list to allow exploration of other branches.

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        results = []
        self.dfs(root, [], results)
        return results
        
    def dfs(self, node, current_path, results):
        current_path.append(str(node.val))
        
        if not node.left and not node.right:
            results.append("->".join(current_path))
            return
        
        if node.left:
            self.dfs(node.left, current_path, results)
            current_path.pop() # Backtrack
            
        if node.right:
            self.dfs(node.right, current_path, results)
            current_path.pop() # Backtrack

Sum of Left Leaves

We need to identify nodes that are left children of their parent and are also leaves. Since we cannot determine if a node is a "left child" from the node itself, we must pass this context from the parent. A post-order traversal works well, accumulating the sum of left leaves found in the subtrees.

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
            
        left_val = self.sumOfLeftLeaves(root.left)
        right_val = self.sumOfLeftLeaves(root.right)
        
        mid_val = 0
        # Check if the left child is a leaf
        if root.left and not root.left.left and not root.left.right:
            mid_val = root.left.val
            
        return mid_val + left_val + right_val

Find Bottom Left Tree Value

The goal is to find the value of the leftmost node in the last row of the tree. We can use a pre-order traversal (root-left-right) while keeping track of the current depth. Since we prioritize the left node, the first time we encounter a depth greater than our recorded maximum, that node is the bottom-left value for that new depth.

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_d = -1
        self.res_val = 0
        self.traverse(root, 0)
        return self.res_val
        
    def traverse(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_d:
                self.max_d = depth
                self.res_val = node.val
            return
        
        if node.left:
            self.traverse(node.left, depth + 1)
        if node.right:
            self.traverse(node.right, depth + 1)

Path Sum

We need to determine if there is a root-to-leaf path where the sum of values equals the target. Instead of accumulating a sum and checking equality, we can decrement the target sum as we traverse down. If we reach a leaf node with a remaining sum of 0, we have found a valid path.

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
            
        # Check if it's a leaf node
        if not root.left and not root.right:
            return targetSum == root.val
            
        # Recurse with reduced target sum
        left_check = self.hasPathSum(root.left, targetSum - root.val)
        right_check = self.hasPathSum(root.right, targetSum - root.val)
        
        return left_check or right_check

Path Sum II

Similar to the previous problem, but we must return all valid paths. This requires maintaining a list of values along the current path. We use backtracking: when a path is complete or invalid, we pop the last value to explore other branches.

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        self.results = []
        self.current_path = []
        self.dfs(root, targetSum)
        return self.results
        
    def dfs(self, node, remaining):
        self.current_path.append(node.val)
        remaining -= node.val
        
        if not node.left and not node.right and remaining == 0:
            self.results.append(list(self.current_path))
            return
        
        if node.left:
            self.dfs(node.left, remaining)
            self.current_path.pop()
            
        if node.right:
            self.dfs(node.right, remaining)
            self.current_path.pop()

Constructing Binary Trees from Traversals

To construct a binary tree from traversal arrays (Preorder/Inorder or Postorder/Inorder), we identify the root element from the Preorder (first element) or Postorder (last element) list. We then find this root's index in the Inorder list to separate the left and right subtrees. The process is repeated recursively for the subarrays.

Preorder and Inorder:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
            
        root_val = preorder[0]
        root = TreeNode(root_val)
        
        # Split point in inorder
        idx = inorder.index(root_val)
        
        # Split inorder
        in_left = inorder[:idx]
        in_right = inorder[idx+1:]
        
        # Split preorder based on inorder sizes
        pre_left = preorder[1:1+len(in_left)]
        pre_right = preorder[1+len(in_left):]
        
        root.left = self.buildTree(pre_left, in_left)
        root.right = self.buildTree(pre_right, in_right)
        
        return root

Maximum Binary Tree

We construct a tree such that the root is the maximum value in the array. The left subtree is constructed from the subarray to the left of the maximum, and the right subtree from the subarray to the right. This is a recursive divide-and-conquer problem.

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
            
        max_val = max(nums)
        max_idx = nums.index(max_val)
        
        root = TreeNode(max_val)
        root.left = self.constructMaximumBinaryTree(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])
        
        return root

Merge Two Binary Trees

We merge two trees by overlapping nodes. If both nodes exist, we sum their values. If one is missing, we use the node from the other tree. This can be done by modifying one of the trees in place to save space.

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
            
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        
        return root1

Searching in a Binary Search Tree (BST)

Leveraging the BST property (left child < root < right child), we can efficiently search for a value. If the target is less than the current node, go left; if greater, go right. If we reach a null node or find the value, we stop.

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        
        if root.val > val:
            return self.searchBST(root.left, val)
        
        return self.searchBST(root.right, val)

Validating a Binary Search Tree

An in-order traversal of a valid BST produces a strictly increasing sequence. We can validate this by tracking the previously visited node. Alternatively, we can pass valid range boundaries (min, max) down the recursion to ensure each node falls within the acceptable interval.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.validate(root, float('-inf'), float('inf'))
        
    def validate(self, node, low, high):
        if not node:
            return True
        
        if node.val <= low or node.val >= high:
            return False
        
        return (self.validate(node.left, low, node.val) and 
                self.validate(node.right, node.val, high))

Minimum Absolute Difference in BST

Since the in-order traversal yields a sorted list of values, the minimum absolute difference will always occur between two adjacent nodes in this traversal. We perform an in-order traversal, keeping track of the previous node's value to calculate the difference.

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        self.prev = None
        self.min_diff = float('inf')
        self.inorder(root)
        return self.min_diff
        
    def inorder(self, node):
        if not node:
            return
        
        self.inorder(node.left)
        
        if self.prev is not None:
            self.min_diff = min(self.min_diff, node.val - self.prev)
        
        self.prev = node.val
        self.inorder(node.right)

Find Mode in BST

The mode is the most frequently occurring value. In a BST, identical values are adjacent during an in-order traversal. We can traverse in-order, counting the frequency of the current value. If the count exceeds the max count, we update the result list. If it equals the max count, we append to the list.

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        self.current_streak = 0
        self.max_streak = 0
        self.prev_val = None
        self.modes = []
        
        self.inorder(root)
        return self.modes
        
    def inorder(self, node):
        if not node:
            return
        
        self.inorder(node.left)
        
        if node.val == self.prev_val:
            self.current_streak += 1
        else:
            self.current_streak = 1
            self.prev_val = node.val
            
        if self.current_streak > self.max_streak:
            self.max_streak = self.current_streak
            self.modes = [node.val]
        elif self.current_streak == self.max_streak:
            self.modes.append(node.val)
            
        self.inorder(node.right)

Lowest Common Ancestor (LCA) of Binary Tree

To find the LCA of nodes p and q, we use post-order traversal. If the current node is p or q, we return it. If the left subtree returns a node and the right subtree returns a node, the current node is the LCA. If only one side returns a node, we propagate that node up.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)
        
        if left_lca and right_lca:
            return root
        
        return left_lca if left_lca else right_lca

LCA in a BST

In a BST, the LCA can be found using the value ordering. If both p and q are smaller than the current node, the LCA is in the left subtree. If both are larger, its in the right subtree. Otherwise, the current node is the LCA (a split point).

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

Insert into a BST

Insertion always happens at a leaf position in a BST. We traverse the tree based on the value to be inserted. When we reach a null pointer where the node should be, we create the new node there.

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
            
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
            
        return root

Delete Node in a BST

Deletion is complex. If the node is a leaf, remove it. If it has one child, replace it with that child. If it has two children, find the minimum value in the right subtree (or max in left), replace the node's value with that value, and recursively delete the duplicate node from the right subtree.

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root
            
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # Node with only one child or no child
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            
            # Node with two children: get inorder successor (min in right subtree)
            current = root.right
            while current.left:
                current = current.left
            root.val = current.val
            root.right = self.deleteNode(root.right, root.val)
            
        return root

Trim a Binary Search Tree

Given a range [low, high], we remove nodes outside this range. If a node's value is less than low, its entire left subtree and itself are invalid, so we return the trimmed right subtree. Similarly, if the value is greater than high, we return the trimmed left subtree.

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
            
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
            
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        
        return root

Convert Sorted Array to Binary Search Tree

A sorted array allows us to create a height-balanced BST by recursively selecting the middle element as the root. The subarray to the left of the middle becomes the left subtree, and the subarray to the right becomes the right subtree.

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def convert(left, right):
            if left > right:
                return None
            
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            node.left = convert(left, mid - 1)
            node.right = convert(mid + 1, right)
            return node
            
        return convert(0, len(nums) - 1)

Convert BST to Greater Tree

The task is to replace every node's value with the sum of all values greater than itself. Since we want to process values from largest to smallest, we perform a reverse in-order traversal (Right - Root - Left), maintaining a running sum of all visited nodes.

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.running_sum = 0
        self.reverse_inorder(root)
        return root
        
    def reverse_inorder(self, node):
        if not node:
            return
        
        self.reverse_inorder(node.right)
        
        # Update node value with running sum
        self.running_sum += node.val
        node.val = self.running_sum
        
        self.reverse_inorder(node.left)