# Binary Tree Tilt

• why can't i view the question from this article? It says access denied.

https://leetcode.com/problems/binary-tree-tilt/

• what is the pictorial binary tree representation of [1,2,3,4,null,5]? and, what is the explanation of its tilt?

• @ardey16 Tilt=4+5+(8-6)=11

``````
1
/  \
2    3
/     /
4     5
``````

• why is it 4+5+(8-6)? shouldnt it be 1+(8-6)=3 ?

• @kekondur
tilt of 4 - 0
tilt of 2- (4-0=4)
tilt of 5- 0
tilt of 3- (5-0=5)
tilt of 1- (8-6=2)
total tilt- 0+4+0+5+2=11

• ``````    pair<int,int>  FindSumTilt(TreeNode* root){
if(root == nullptr){
return make_pair(0,0);
}

auto left_res = FindSumTilt(root->left);
auto right_res = FindSumTilt(root->right);

int sum = left_res.first + right_res.first + root->val;
int tilt = left_res.second + right_res.second + abs(left_res.first - right_res.first);
return make_pair(sum,tilt);
}
int findTilt(TreeNode* root) {
if(root == nullptr){
return 0;
}
auto res = FindSumTilt(root);
return res.second;
}
``````

• Less then 10 lines C# code
public int FindTilt(TreeNode root)
{
if (root == null)
return 0;
return Math.Abs(SumNode(root.left) - SumNode(root.right)) + FindTilt(root.left) + FindTilt(root.right);
}

``````    int SumNode(TreeNode node)
{
if (node == null)
return 0;
return node.val + SumNode(node.left) + SumNode(node.right);
}``````

• C++ solution O(n)

``````class Solution {
public:

// tiltDFS returns sum and accumulate tilt of each node
int tiltDFS(TreeNode *root, int &tilt)
{
if (!root)
return 0;

// Traverse left
int sumLeft = tiltDFS(root->left, tilt);

// Traverse right
int sumRight = tiltDFS(root->right, tilt);

// Calculate current tilt and add to total tilt
tilt += abs(sumLeft - sumRight);

// return sum of node values up to this node
return (sumLeft + sumRight + root->val);
}

int findTilt(TreeNode *root)
{
if (!root)
return 0;
int TL, TR, SR, SL;
TL = TR = SL = SR = 0;

// Get left tilt and sum of left nodes
SL = tiltDFS(root->left, TL);

// Get right tilt and sum of right nodes
SR = tiltDFS(root->right, TR);

return (abs(SR - SL) + TL + TR);
}
};
``````

• Something is not correct either in the question or the answer. The question states that the tilt is: "The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values". With that definition, tilt of root will be `|sum(left) - sum(right)|`. However this answer states that the root's tilt is `root.val + |sum(left) - sum(right)|`. Please advise if I am missing something here.

• Did the exact thing in python. Hurrah

• JS without global variable:

var findTilt = function(root) {
return treeTilt(root, { val: 0 });
};

var treeTilt = function(root, sum) {
if (root === null) {
return 0;
}

``````var leftSum = { val: 0 };
var rightSum = { val: 0 };
var leftTilt = treeTilt(root.left, leftSum);
var rightTilt = treeTilt(root.right, rightSum);
sum.val = root.val + leftSum.val + rightSum.val;

return leftTilt + rightTilt + Math.abs(leftSum.val - rightSum.val);
``````

}

• Everybody knows the recursive - the trick is in the return statement: (left+right+val) -- it's not the tilt but return value. Actually it covers every situations of a given note - it works. But nobody explains or even mention it in their solution.

• Ugly solution with the use of helper field. Doesn't support multiple calls, not thread safe etc. It seems number of lines is the only criteria of success on leetcode instead of readability and maintainability

• Doesn't work for [1,2].

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.