Diameter, Height, and Balanced Trees
Compute tree diameter and height in a single DFS pass using a helper that returns both values, then check if a tree is height-balanced.
Height of a Binary Tree
The height (or maximum depth) of a binary tree is the length of the longest path from the root to any leaf. It is computed recursively: the height of any node is 1 + max(height(left), height(right)), with a base case of 0 for null nodes. This post-order computation is fundamental — height is the building block for diameter, balance-checking, and AVL tree rotations.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4Diameter: The Longest Path
The diameter of a binary tree is the length of the longest path between any two nodes (the path may or may not pass through the root). The path length is measured in edges. For any node, the diameter through that node equals height(left) + height(right). The overall diameter is the maximum such value across all nodes in the tree.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3All lessons in this course
- TreeNode Class and Level-Order BFS
- In-Order, Pre-Order, Post-Order DFS
- Diameter, Height, and Balanced Trees
- Path Sum and Lowest Common Ancestor