Height, Diameter and Balance
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Height, diameter and balance are questions about the shape of a tree. All three come from one idea: ask each child for its height, then combine the answers. This lesson also shows the slow way first, so you see why one pass is better.
Height: ask both children
Height of a tree is the length of the longest path from the root down to a leaf. This module counts it in nodes, so an empty tree has height 0 and a single node has height 1.
A tree is as tall as its taller subtree plus the node itself. Ask each child for its height, take the larger answer and add one. A missing child has height 0.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0print(height(root))Example 1 · Height in nodes and in edges
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0
print(height(None), height(TreeNode(7)), height(root))print("edges:", height(root) - 1)0 1 3 edges: 2
What this code does
- An empty tree has height 0 and a single node has height 1. The sample tree has three rows, so its height is 3.
- In edges the height is one less. Always check which count a problem asks for.
Example 2 · Height from the rows
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def height(root): queue, rows = deque([root] if root else []), 0 while queue: rows += 1 for _ in range(len(queue)): node = queue.popleft() queue.extend(c for c in (node.left, node.right) if c) return rows
print(height(root))3
What this code does
- The height is the number of rows. This needs no recursion, so deep trees are safe.
- Space is O(w) for the widest row instead of O(h).
Here height counts nodes on the longest path from the root down, so a single node has height 1. In edges, subtract one. Time is O(n) and stack space is O(h).
Diameter: the longest path between two nodes
Diameter of a tree is the number of edges on the longest path between any two of its nodes. The path may pass through the root or stay inside one subtree.
The longest path may bend at any node and does not have to use the root. At each node, the best path that bends there is the left height plus the right height. Record the best while computing heights.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightdef diameter(root): best = 0 def height(node): nonlocal best if node is None: return 0 left, right = height(node.left), height(node.right) best = max(best, left + right) return 1 + max(left, right) height(root) return bestprint(diameter(TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))))Example 3 · Diameter, the slow way
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0
def diameter(node): if node is None: return 0 through = height(node.left) + height(node.right) return max(through, diameter(node.left), diameter(node.right))
print(diameter(root))4
What this code does
- At each node it asks for both heights again, and
heightwalks the whole subtree. - On a chain of n nodes that is O(n squared). The one-pass version fixes it.
Example 4 · A longest path that avoids the root
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
root = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(5)), TreeNode(4, None, TreeNode(6))))def diameter(root): best = 0
def height(node): nonlocal best if node is None: return 0 left, right = height(node.left), height(node.right) best = max(best, left + right) return 1 + max(left, right)
height(root) return best
print(diameter(root))4
What this code does
- The path 5, 3, 2, 4, 6 has 4 edges and bends at node 2.
- Through the root the best path has only 3 edges, so using root heights alone would give a wrong answer.
The path 4, 2, 1, 3 has 3 edges, so the diameter is 3. One pass of O(n) time does the work. Calling height again at every node would give O(n squared) on a chain.
Balanced: heights that stay close
Balanced binary tree means that at every node the heights of the left and right subtrees differ by at most 1. A balanced tree with n nodes has height about log n, so searches stay fast.
A tree is balanced when, at every node, the two subtree heights differ by at most 1. Compute heights from the bottom and return -1 as soon as one node breaks the rule. The -1 then travels upward.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def check(node): if node is None: return 0 left, right = check(node.left), check(node.right) if left < 0 or right < 0 or abs(left - right) > 1: return -1 return 1 + max(left, right)print(check(root) != -1)Example 5 · Balanced check: slow and fast
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def build(tokens): nodes = [None if t == "null" else TreeNode(int(t)) for t in tokens] kids = iter(nodes[1:]) for node in nodes: if node: node.left, node.right = next(kids, None), next(kids, None) return nodes[0]
def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0
def slow(node): if node is None: return True return abs(height(node.left) - height(node.right)) <= 1 and slow(node.left) and slow(node.right)
def check(node): if node is None: return 0 left, right = check(node.left), check(node.right) if left < 0 or right < 0 or abs(left - right) > 1: return -1 return 1 + max(left, right)
for text in ["3 9 20 null null 15 7", "1 2 2 3 3 null null 4 4", "1 2 null 3"]: root = build(text.split()) print(slow(root), check(root) != -1)True True False False False False
What this code does
- Both give the same answers. The slow one repeats height work at every node.
- The fast one returns -1 at the first broken node and every caller above passes it on.
Example 6 · A balanced tree from sorted values
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def balanced(values): if not values: return None mid = len(values) // 2 return TreeNode(values[mid], balanced(values[:mid]), balanced(values[mid + 1:]))
def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0
root = balanced(list(range(1, 16)))print(root.val, height(root))chain = Nonefor v in range(15, 0, -1): chain = TreeNode(v, None, chain)print(chain.val, height(chain))8 4 1 15
What this code does
- Taking the middle value as the root keeps both halves the same size. Fifteen values fit in 4 rows.
- The same fifteen values inserted in order make a chain of 15 rows. Balance is what keeps height near log n.
Every node is looked at once, so time is O(n). The simple way, calling height at every node, is O(n squared) for a chain.
Very deep trees
Python allows about 1000 nested calls. A tree shaped like a chain of 3000 nodes breaks a recursive height. Raise the limit with sys.setrecursionlimit for contest-style tests, or use a stack.
import syssys.setrecursionlimit(10000)class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = Nonefor i in range(3000): root = TreeNode(i, root)def height(node): return 1 + max(height(node.left), height(node.right)) if node else 0print(height(root))Example 7 · Iterative height with a stack
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
root = Nonefor i in range(3000): root = TreeNode(i, root)best, stack = 0, [(root, 1)]while stack: node, depth = stack.pop() best = max(best, depth) for child in (node.left, node.right): if child: stack.append((child, depth + 1))print(best)3000
What this code does
- Each stack item carries its depth, so no call stack is used and no limit needs to be raised.
- This also solves the 3000-node chain from the last section.
Raising the limit is fine for tests of moderate depth. For very deep trees an iterative version with its own stack is safer, as the examples show.
Next step
Check your understanding
12 quick questions