Dynamic Programming on Trees

Definition

DP on Trees involves solving a problem for a root node by combining results from its children sub-trees. It’s essentially “Post-Order Traversal” (Left, Right, Root) combined with DP logic.

How it Works

1. Leaf Nodes: These are the base cases (e.g., diameter is 0).
2. Recursive Step: For a node u, calculate the answer based on answers from children v1, v2….
3. Example Problem (Diameter of Tree): The longest path between any two nodes. The path either passes through the root or is entirely inside one of the sub-trees.

Example Logic (Tree Diameter)

For every node, calculate:

1. Height of left subtree (L).
2. Height of right subtree (R).
3. Diameter passing through this node = L + R + 1.
4. Update global maximum diameter.
5. Return max(L, R) + 1 to the parent.

Code Example (Java – Pseudo-ish)

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class DiameterOfTree {

    // Function to calculate diameter
    public static int diameter(Node root, int[] res) {
        if (root == null) {
            return 0;
        }

        // Get height of left and right subtrees
        int l = diameter(root.left, res);
        int r = diameter(root.right, res);

        // Update global result if path through root is larger
        res[0] = Math.max(res[0], l + r + 1);

        // Return height of this node
        return Math.max(l, r) + 1;
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);

        int[] res = new int[]{-1}; // Mutable reference

        diameter(root, res);

        System.out.println("Diameter is " + res[0]);
    }
}

Complexity Analysis

• Time Complexity: O(N. We visit every node once.
• Space Complexity: O(H) where H is the height of the tree (recursion stack).

Use Cases

• Network Routing: Finding optimal paths in hierarchical networks.
• Company Hierarchy: Calculating total salary of a department (subtree sum).