Greatest difference Left and Right subtree count Node

Find the node with the max difference in the total number o0f descendents in its left subtree and right subtree.

Solution: sinking check, backtracking against global var

Base Case: if node == null: return 0;

Recursive rule:

From Children: receive number of nodes below

For current node: Check current left right diff against global max. If greater, update global max, add self to solution node

To parents: pass left count + right count + 1

public TreeNode solve(TreeNode root){
    TreeNode[] solution = TreeNode[1]; //avoid pass by ref
    int[] globalDiff = {Integer.MIN_VALUE};
    
    
    maxlrdiffNode(root, globalDiff, solution);
    
    return solution[0];
}

public int maxlrdiffNode(TreeNode root, int[] globalDiff, TreeNode[] sol){
    if (root == null) return 0;
    int leftCount = maxlrdiffNode(root.left);
    int rightCount = maxlrdiffNode(root.right);
    
    //check against global max
    int curDiff = Math.abs(leftCount - rightCount);
    
    if (curDiff > globalDiff[0]){
        globalDiff[0] = curDiff;
        sol[0] = root;
    }
    
    return leftCount + rightCount + 1;
}
    

Time Complexity: O(2^N) 2 recursive calls per node

Space Complexity: O(Height) recursive call stack