Binary Trees II: Advanced Tree Operations

Level-order Traversal

Tree Paths and Properties

Java Implementation

import java.util.*;

public class LevelOrderTraversal {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int x) { 
            val = x; 
        }
    }
    
    public static List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
    
    // Driver code to test the implementation
    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        
        // Perform level-order traversal
        List> levels = levelOrder(root);
        
        // Print the result
        for (int i = 0; i < levels.size(); i++) {
            System.out.println("Level " + i + ": " + levels.get(i));
        }
    }
}

Finding All Root-to-Leaf Paths

import java.util.*;

public class TreePaths {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int x) { 
            val = x; 
        }
    }
    
    public static List binaryTreePaths(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        findPaths(root, "", result);
        return result;
    }
    
    private static void findPaths(TreeNode node, String currentPath, List paths) {
        if (node == null) {
            return;
        }
        
        // Add current node to the path
        String updatedPath = currentPath.isEmpty() 
            ? String.valueOf(node.val) 
            : currentPath + "->" + node.val;
        
        // If it's a leaf node, add the complete path to the result
        if (node.left == null && node.right == null) {
            paths.add(updatedPath);
            return;
        }
        
        // Recurse for left and right subtrees
        findPaths(node.left, updatedPath, paths);
        findPaths(node.right, updatedPath, paths);
    }
    
    // Calculate tree diameter (longest path between any two nodes)
    public static int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int[] diameter = new int[1];
        calculateHeight(root, diameter);
        return diameter[0];
    }
    
    private static int calculateHeight(TreeNode node, int[] diameter) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = calculateHeight(node.left, diameter);
        int rightHeight = calculateHeight(node.right, diameter);
        
        // Update diameter if path through current node is longer
        diameter[0] = Math.max(diameter[0], leftHeight + rightHeight);
        
        // Return height of current subtree
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    // Driver code to test the implementations
    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        
        // Find all root-to-leaf paths
        List paths = binaryTreePaths(root);
        System.out.println("All root-to-leaf paths: " + paths);
        
        // Calculate tree diameter
        int diameter = diameterOfBinaryTree(root);
        System.out.println("Tree diameter: " + diameter);
    }
}

Guided Practice

For additional hands-on practice and advanced exercises on binary trees, check out our comprehensive guided project:

• Guided Project: Binary Trees