algoadvance

Leetcode 563. Binary Tree Tilt

Problem Statement

Given the root of a binary tree, return the sum of every tree node’s 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. If a node does not have a left child, then the sum of the left subtree is considered to be 0. The rule is similar if there is no right child.

Example:

Given the following tree:

        1
      /   \
     2     3

• The tilt of node 2 is 0 as it doesn’t have any children and the sum of their hypothetical children is 0.
• The tilt of node 3 is 0 as it doesn’t have any children and the sum of their hypothetical children is 0.

• The tilt of node 1 is

  2 - 3

  = 1.

So, the output is 1.

Clarifying Questions

1. What is the definition of a node tilt?
   • The tilt of a node is the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values.
2. What should we return for an empty tree?
   • For an empty tree, the sum of tilts is 0.
3. Can the tree contain negative values?
   • Yes, the problem does not specify that values must be positive.
4. Are duplicate values allowed in the tree?
   • Yes, binary tree nodes can have duplicate values.

Strategy

To solve this problem, we will use a Depth First Search (DFS) traversal. Here’s the detailed plan:

1. Define a helper function: Create a recursive function dfs that will calculate the sum of node values for the subtree rooted at the current node, and in the process, compute the tilt for each node and keep track of the cumulative tilt.

2. Base Case: If the current node is nullptr, return 0 as the sum of node values.

3. Recursive Case:
   • Calculate the sum of values for the left subtree.
   • Calculate the sum of values for the right subtree.
   • Calculate the tilt for the current node (absolute difference between left and right subtree sums).
   • Add the current node’s tilt to the overall tilt.
   • Return the sum of the current node’s value and its left and right subtree sums.
4. Main Function: Start the DFS traversal from the root node and return the accumulated tilt.

Code

Here is the implementation of the above strategy in C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    // Function to calculate the tilt of the tree
    int findTilt(TreeNode* root) {
        int totalTilt = 0;
        dfs(root, totalTilt);
        return totalTilt;
    }
    
private:
    // DFS helper function to compute the sum and tilt
    int dfs(TreeNode* node, int& totalTilt) {
        if (!node) return 0;  // Base case: a null node contributes 0 to the sum
        
        // Get sums from left and right subtrees
        int leftSum = dfs(node->left, totalTilt);
        int rightSum = dfs(node->right, totalTilt);
        
        // Calculate the tilt of the current node
        int nodeTilt = abs(leftSum - rightSum);
        
        // Add the node's tilt to the total tilt
        totalTilt += nodeTilt;
        
        // Return the sum of values for the subtree rooted at this node
        return node->val + leftSum + rightSum;
    }
};

Time Complexity

• Time Complexity: ( O(N) )
  • Each node in the tree is visited once (DFS Traversal), so the time complexity is linear with respect to the number of nodes N in the tree.
• Space Complexity: ( O(H) )
  • The space complexity is determined by the recursion stack, which in the worst case scenario (a completely unbalanced tree) can go up to the height H of the tree. For a balanced tree, this is typically O(log N), where N is the number of nodes.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?