Binary Tree Tilt

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 all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have the right child.

Example:

Input:  tree: {1,2,3}
Output: 1

Approach

Java

public class BinaryTreeTilt {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(findTilt(root));
    }

    static int sum;

    static int findTilt(TreeNode root) {
        sum=0;
        dfs(root);
        return sum;
    }

    static int dfs(TreeNode root) {
        // base case if tree is empty
        if (root == null)
            return 0;

        // call for left subtree
        int leftsum = dfs(root.left);

        // call for right subtree
        int rightsum = dfs(root.right);
        sum += Math.abs(leftsum - rightsum);
        return leftsum + rightsum + root.val;
    }

}


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;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

int  dfs(TreeNode *root,int &sum)
{
    //base case if tree is empty
    if(root==NULL)
        return 0;

    //call for left subtree
    int leftsum=dfs(root->left,sum);

    //call for right subtree
    int rightsum=dfs(root->right,sum);
    sum+=abs(leftsum-rightsum);
    return leftsum+rightsum+root->data;
}
int findTilt(TreeNode* root)
{
        int sum=0;
        int c=dfs(root,sum);
        return sum;
}

int main()
{
     TreeNode *root=new TreeNode(1);
     root->left=new TreeNode(2);
     root->right=new TreeNode(3);
     cout<<findTilt(root);
     return 0;
}