700696. Tilt of Binary Tree
Tilt of Binary Tree
Slug: tilt-of-binary-tree Difficulty: Easy Id: 700696 Topic Tags: Tree, Data Structures Company Tags: None
Summary
The Tilt of Binary Tree problem involves calculating the total absolute difference between left and right children of each node in a binary tree. This difference is known as the tilt of each node.
Given a binary tree, we need to calculate the total tilt of all nodes in the tree. The tilt of a node is defined as the absolute difference between its left child's value and its right child's value.
Detailed Explanation
To solve this problem, we will perform an in-order traversal of the binary tree. This traversal allows us to visit all the nodes in the tree while maintaining the correct order (left-root-right).
Here's a step-by-step breakdown of the solution:
- Start at the root node.
- Traverse left subtree recursively until you reach a leaf node or the left child is null.
- At each node, calculate the tilt by subtracting the value of the right child from the value of the left child.
- Add this tilt to the total tilt.
- Repeat steps 1-4 for all nodes in the tree.
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(h), where h is the height of the tree (in case of a skewed tree).
Optimized Solutions
Java
class Solution {
int sum = 0;
public int findTilt(TreeNode root) {
helper(root);
return sum;
}
private void helper(TreeNode node) {
if (node == null) {
return;
}
int leftSum = getSum(node.left);
int rightSum = getSum(node.right);
sum += Math.abs(leftSum - rightSum);
helper(node.left);
helper(node.right);
}
private int getSum(TreeNode node) {
if (node == null) {
return 0;
}
return node.val + getSum(node.left) + getSum(node.right);
}
}