Binary Tree: Property-Based Challenges

Mental Model for Tree Properties

Property-based tree problems typically employ Post-order Traversal (Bottom-up approach: subproblems report information to the parent).

The critical questions to ask for each node are:

1. What information do I need from my subtrees?
2. What information should I return to my parent?

Height and Depth

Maximum Depth (LeetCode 104)

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Minimum Depth (LeetCode 111)

The minimum depth is the length of the shortest path to a leaf node. Caution: nodes with only one child are not leaves—you cannot simply take the minimum of both paths.

int minDepth(TreeNode root) {
    if (root == null) return 0;
    // Base case: Leaf node
    if (root.left == null && root.right == null) return 1;
    // If one subtree is null, only the other path leads to a leaf
    if (root.left == null) return 1 + minDepth(root.right);
    if (root.right == null) return 1 + minDepth(root.left);
    
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

Balanced Trees and Diameter

Balanced Binary Tree (LeetCode 110)

A balanced tree is one where the height of the two subtrees of every node never differs by more than 1.

boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

// Returns height if balanced; otherwise returns -1
int height(TreeNode node) {
    if (node == null) return 0;
    
    int leftHeight = height(node.left);
    if (leftHeight == -1) return -1;
    
    int rightHeight = height(node.right);
    if (rightHeight == -1) return -1;
    
    // Check balance condition at current node
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Diameter of Binary Tree (LeetCode 543)

Definition: The longest path between any two nodes.
Relationship: Diameter = leftHeight + rightHeight for some node in the tree.

int maxDiameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    calculateDepth(root);
    return maxDiameter;
}

int calculateDepth(TreeNode node) {
    if (node == null) return 0;
    int l = calculateDepth(node.left);
    int r = calculateDepth(node.right);
    
    // Update global max using results from subtrees
    maxDiameter = Math.max(maxDiameter, l + r);
    
    return 1 + Math.max(l, r);
}

Path Sums

Root-to-Leaf Path Sum Existence (LeetCode 112)

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    // If leaf, check if the remaining target matches node value
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

Find All Root-to-Leaf Path Sums (LeetCode 113)

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), result);
    return result;
}

void dfs(TreeNode node, int remain, List<Integer> currentPath, List<List<Integer>> res) {
    if (node == null) return;
    
    currentPath.add(node.val);
    
    // If leaf and path matches target
    if (node.left == null && node.right == null && remain == node.val) {
        res.add(new ArrayList<>(currentPath)); // Deep copy current state
    }
    
    dfs(node.left, remain - node.val, currentPath, res);
    dfs(node.right, remain - node.val, currentPath, res);
    
    currentPath.remove(currentPath.size() - 1); // Backtrack
}

Binary Tree Maximum Path Sum (LeetCode 124)

Paths can be non-root, but must be contiguous.

int maxPathVal = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    getOneSideMax(root);
    return maxPathVal;
}

// Returns the maximum contribution from current node extending along ONE side
int getOneSideMax(TreeNode node) {
    if (node == null) return 0;
    
    // Max of 0 ensures we ignore subpaths with a negative sum contribution
    int leftMax = Math.max(0, getOneSideMax(node.left));
    int rightMax = Math.max(0, getOneSideMax(node.right));
    
    // Update global maximum considering the current node as the path peak
    maxPathVal = Math.max(maxPathVal, node.val + leftMax + rightMax);
    
    // Report single-side max back to the parent
    return node.val + Math.max(leftMax, rightMax);
}

Other Property Challenges

Symmetric Tree (LeetCode 101)

boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    return (l.val == r.val)
        && isMirror(l.left, r.right)
        && isMirror(l.right, r.left);
}

Invert Binary Tree (LeetCode 226)

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tempLeft = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tempLeft);
    return root;
}

Lowest Common Ancestor (LeetCode 236)

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    
    TreeNode leftFound = lowestCommonAncestor(root.left, p, q);
    TreeNode rightFound = lowestCommonAncestor(root.right, p, q);
    
    // If p and q are found in different subtrees, current node is the LCA
    if (leftFound != null && rightFound != null) return root;
    
    // Otherwise, return whichever child subtree contains target(s)
    return leftFound != null ? leftFound : rightFound;
}

Pattern Summary