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.
Diameter, Height, and Balanced Trees is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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)) # 3Single DFS Pass for Diameter
The naive approach calls height() at every node — O(n²) for a balanced tree. The optimal solution computes height and updates the diameter in a single DFS pass. The key insight is that the recursive dfs() function serves two purposes simultaneously: it returns the height for the parent while updating a global max diameter as a side effect. This dual-purpose post-order pattern appears in many tree problems.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')Balanced Binary Tree Check
A binary tree is height-balanced if the heights of the left and right subtrees of every node differ by at most one. The brute-force approach calls height() at every node — O(n²). The optimal approach uses the same single-pass trick: return -1 as a sentinel for 'unbalanced' and propagate it up, pruning early as soon as any node is found unbalanced.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # FalseThe Sentinel Return Value Pattern
Returning a sentinel value (-1 for unbalanced, or a special tuple) is a common pattern when a DFS helper needs to signal two kinds of information: the computed result and whether a constraint was violated. Instead of raising exceptions or using global flags, encode the error in the return type. This approach is clean, avoids global state, and composes naturally with other recursive helpers.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2Diameter in Terms of Nodes vs Edges
Be careful with the problem statement: LeetCode #543 measures diameter in edges, while some problems measure in nodes. If you need node-count, the diameter through a node is height(left) + height(right) + 1 (add 1 for the node itself). If you need edge-count, omit the +1. Always clarify this with your interviewer before coding.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3Path Sum: Any Root-to-Leaf Path
The path sum problem asks: does any root-to-leaf path sum equal a target value? Use DFS and subtract the current node's value from the target as you descend. At a leaf, check if the remaining target equals the leaf's value. This is a pre-order DFS where you pass the remaining sum as a parameter — a classic example of top-down recursion.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22Maximum Path Sum (Hard Variant)
The maximum path sum (LeetCode #124) is significantly harder: the path can start and end at any node, not just root-to-leaf, and values can be negative. At each node, consider four options: just the node itself, node + left branch, node + right branch, or node + both branches. Only the first three can extend upward to the parent; the fourth is a terminal candidate for the global maximum.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7AVL Trees and Self-Balancing
An AVL tree is a BST that maintains the height-balance property by performing rotations after insert and delete operations. Each node stores a balance factor (height(right) - height(left)), which must stay in {-1, 0, 1}. When a violation occurs, a single or double rotation restores balance in O(1) time, keeping the overall height at O(log n) and all operations at O(log n) guaranteed.
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')Symmetric Tree Check
A binary tree is symmetric if it is a mirror image of itself. Check recursively: the tree is symmetric if, for every pair of corresponding nodes across the axis, they have equal values and their subtrees mirror each other. Define a helper is_mirror(left, right) that checks: both null (ok), one null (not ok), values equal and inner/outer subtrees mirror.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # FalseCombining Height and Diameter Insights
The single-pass post-order pattern where a helper simultaneously returns height and updates a global result is reusable across many problems: diameter, maximum path sum, check balance, count good nodes, and more. Always ask: 'what information does the parent need from each child?' That is the return value. 'What computation is local to this node?' That updates the global answer. This decomposition is the key skill for hard tree problems.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: height computation using recursive post-order DFS, diameter calculation in a single O(n) pass using a dual-purpose DFS helper, and balance checking with an early-exit sentinel. Next up we tackle path sum problems and lowest common ancestor.
Frequently asked questions
Is the “Diameter, Height, and Balanced Trees” lesson free?
Yes — the full text of “Diameter, Height, and Balanced Trees” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Diameter, Height, and Balanced Trees” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All 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