algoadvance

Leetcode 563. Binary Tree Tilt

Problem Statement

Given the root of a binary tree, return the tilt of the whole tree.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Clarifying Questions

  1. What is the definition of a binary tree tilt?
    • The tilt of a tree node is the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values.
    • The tilt of the whole tree is the sum of tilts of all individual nodes.
  2. Can the tree contain negative values?
    • Yes, assume the tree can contain any integer values, including negative numbers.
  3. What are the constraints on the size of the tree?
    • This problem typically handles trees that fit within standard recursion limits. Assume the number of nodes n in the tree is reasonably small (e.g., n <= 10,000).

Strategy

The main idea is to traverse the tree in a post-order manner (i.e., process children before the node itself), compute the tilt for each node, and accumulate these tilts for the final result. Post-order traversal ensures that when computing the tilt for a particular node, you have already computed the values of its children.

  1. Define a helper function that computes the sum of the subtree rooted at a given node.
  2. This helper function should also compute the tilt for each node and add it to a global variable that keeps track of the total tilt of the tree.

Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        computeTilt(root);
        return totalTilt;
    }

    private int computeTilt(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = computeTilt(node.left);
        int rightSum = computeTilt(node.right);

        int nodeTilt = Math.abs(leftSum - rightSum);
        totalTilt += nodeTilt;

        return node.val + leftSum + rightSum;
    }

    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node2 = new TreeNode(2, node3, node5);
        TreeNode node4 = new TreeNode(4);
        TreeNode root = new TreeNode(1, node2, node4);

        Solution solution = new Solution();
        System.out.println(solution.findTilt(root));  // Output the tilt of the whole tree
    }
}

Time Complexity

This approach efficiently computes the tilt of the binary tree within the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI