How to determine if a binary tree is height-balanced?
If the height disparity between a binary tree's left and right subtrees is one or less and both of those subtrees are height-balanced, the binary tree is said to be height-balanced.
Here is a Python method to determine if a binary tree is symmetrical in height:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_balanced(root: TreeNode) -> bool:
if not root:
return True
def height(node):
if not node:
return 0
left_height = height(node.left)
right_height = height(node.right)
return 1 + max(left_height, right_height)
left_height = height(root.left)
right_height = height(root.right)
if abs(left_height - right_height) > 1:
return False
return is_balanced(root.left) and is_balanced(root.right)
The function gives the binary tree's base node as input. If the tree's height is equal, the value is True; otherwise, it is False.
The main function determines whether the height disparity between the left and right subtrees is one or less, and the height() function iteratively calculates the height of the tree rooted at node. Lastly, the function iteratively determines whether the heights of the left and right subtrees are also equal.
You can test the function with the following code:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(is_balanced(root)) # Output: False
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(is_balanced(root))
Output:
True
To determine if a binary tree is height-balanced, we can use a recursive approach to check the height of each subtree and compare their heights to determine if the tree is balanced.
A binary tree is height-balanced if there is no more than a one-unit disparity between the heights of its left and right subtrees for each node in the tree.
The following Python code tests whether a binary tree is height-balanced:
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_height_balanced(root):
if root is None:
return True
# Check the height difference of the left and right subtree
left_height = get_height(root.left)
right_height = get_height(root.right)
if abs(left_height - right_height) > 1:
return False
# Recursively check if the left and right subtrees are balanced
return is_height_balanced(root.left) and is_height_balanced(root.right)
def get_height(node):
if node is None:
return 0
# Recursively get the height of the left and right subtrees
left_height = get_height(node.left)
right_height = get_height(node.right)
# Return the height of the subtree rooted at the current node
return max(left_height, right_height)
The Node class is used to represent the nodes of the binary tree. The is_height_balanced function takes the root node of the binary tree as input and recursively checks if each node in the tree is height-balanced.
The get_height function is a helper function that recursively calculates the height of a subtree rooted at a given node.
The is_height_balanced function first checks if the root node is None, in which case it returns True. It then calculates the height of the left and right subtrees using the get_height function and checks if the difference in height is greater than 1. If it is, the function returns False.
If the height difference is less than or equal to 1, the function recursively checks if the left and right subtrees are height-balanced by calling is_height_balanced on each subtree.
The method gives True if both subtrees are height-balanced; otherwise, it returns False.
A binary tree must have a height disparity between the left and right subtrees of each node of the tree of no more than one to be considered height-balanced.
We can use recursion to calculate the height of each subtree and compare them to determine if the tree is height-balanced. Here's an implementation in Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_balanced(root: TreeNode) -> bool:
"""
Returns True if the binary tree rooted at root is height-balanced, False otherwise.
"""
if not root:
return True
left_height = get_height(root.left)
right_height = get_height(root.right)
if abs(left_height - right_height) > 1:
return False
return is_balanced(root.left) and is_balanced(root.right)
def get_height(node: TreeNode) -> int:
"""
Returns the height of the binary tree rooted at node.
"""
if not node:
return 0
left_height = get_height(node.left)
right_height = get_height(node.right)
return max(left_height, right_height)
The is_balanced function takes the root of the binary tree as input and returns True if the tree is height-balanced, and False otherwise.
It first checks if the root is null and returns True if it is. It then calculates the heights of the left and right subtrees using the get_height function and checks if their difference is greater than 1.
If it is, then the tree is not height-balanced and the function returns False. If not, it repeatedly checks to see if the left and right subtrees are height-balanced and then returns the logical AND of the two outcomes.
The get_height function takes a node as input and returns the height of the binary tree rooted at that node. It first checks if the node is null and returns 0 if it is. It then recursively calculates the heights of the left and right subtrees and returns the maximum of the two plus 1.