Determine if a binary tree is considered 'well-proportioned' - meaning that for every node, the heights of its left and right subtrees are within a certain tolerance. This is a common tree problem that tests your understanding of recursion and tree traversals.
Given the root of a binary tree and a maximum allowed height difference, determine if the tree is 'well-proportioned'. A binary tree is well-proportioned if, for every node in the tree, the absolute difference in height between its left and right subtrees is less than or equal to the given maximum allowed difference. Return True if the tree is well-proportioned, and False otherwise.
The brute force approach involves calculating the height of the left and right subtrees for every node in the tree. For each node, we would recursively compute the height of both subtrees and check if the difference exceeds the maximum allowed difference. If it does, we know the tree is not well-proportioned. Like inspecting every item in a warehouse for defects one by one, this is simple but inefficient. This approach has a time complexity of O(n^2) because for each node, we are potentially traversing the entire subtree to calculate its height. The space complexity is O(n) in the worst case, due to recursion depth.
Work through this problem with AI coaching and get real-time feedback
Practice This Problem