DSA Diameter of a Binary Tree
The diameter of a binary tree is the longest path between any two nodes in the tree. The path counts its edges, and it does not have to pass through the root.
The problem
The diameter of a binary tree is the largest number of edges on any path between two nodes. A path runs between two nodes through their shared ancestors. The longest path does not have to pass through the root.
Height is the longest downward path in edges from a node into its own subtree. A leaf has height 0. An empty child has height -1, which keeps the edge counts below exact.
The cases used in this article
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
balanced = TreeNode(5,
TreeNode(3, TreeNode(1), TreeNode(4)),
TreeNode(8, TreeNode(7), TreeNode(9)))
chain = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
deep_left = TreeNode(10,
TreeNode(5,
TreeNode(3, TreeNode(2, TreeNode(1))),
TreeNode(8, TreeNode(9, TreeNode(11)))),
TreeNode(12))
single = TreeNode(42)
for name, tree, edges, path in [
("balanced", balanced, 4, [1, 3, 5, 8, 7]),
("chain", chain, 3, [4, 3, 2, 1]),
("deep left", deep_left, 6, [1, 2, 3, 5, 8, 9, 11]),
("single node", single, 0, [42])]:
print(name, "- diameter:", edges, "edges, path:", path)Read one row at a time. The balanced tree answers through its root. The deep left tree answers inside its left subtree, far from its root.
Intuition: measure the path through one node
A path through a node joins the longest downward path on its left with the longest downward path on its right. The join adds two edges. Those edges link the node to its two children.
Checking only the root is the trap. The root of the deep left tree gives a path of five edges. The true diameter is six, and it never reaches the root.
The path through the root of the deep left tree
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
deep_left = TreeNode(10,
TreeNode(5,
TreeNode(3, TreeNode(2, TreeNode(1))),
TreeNode(8, TreeNode(9, TreeNode(11)))),
TreeNode(12))
left_height = height(deep_left.left)
right_height = height(deep_left.right)
print("left height below root:", left_height)
print("right height below root:", right_height)
print("path through root:", left_height + right_height + 2, "edges")
print("diameter of the whole tree: 6 edges")Every node offers one candidate path. The diameter is the best candidate over all nodes. The search therefore has to visit every node, not only the root.
Brute force: a fresh height for every node
The brute force lists every node first. It then computes the height of each side of each node from scratch. A counter records how many nodes those height calls visit.
The method always works. Its cost is the repeated work. One height call rewalks a whole subtree, and later nodes rewalk much of the same ground.
The brute force, with its height visits counted
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node, visits):
if node is None:
return -1
visits[0] += 1
return 1 + max(height(node.left, visits), height(node.right, visits))
def collect(node, nodes):
if node is None:
return
nodes.append(node)
collect(node.left, nodes)
collect(node.right, nodes)
def diameter_brute(root):
nodes = []
collect(root, nodes)
visits = [0]
best = 0
for node in nodes:
through = height(node.left, visits) + height(node.right, visits) + 2
if through > best:
best = through
return best, visits[0]
balanced = TreeNode(5,
TreeNode(3, TreeNode(1), TreeNode(4)),
TreeNode(8, TreeNode(7), TreeNode(9)))
chain = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
deep_left = TreeNode(10,
TreeNode(5,
TreeNode(3, TreeNode(2, TreeNode(1))),
TreeNode(8, TreeNode(9, TreeNode(11)))),
TreeNode(12))
for name, tree in [("balanced", balanced), ("chain", chain), ("deep left", deep_left)]:
edges, visits = diameter_brute(tree)
print(name, "- diameter:", edges, "height visits:", visits)The chain is the painful shape. Each new height call starts near the top of a long line of nodes. The deep left tree pays for its tall left subtree again and again.
The optimal solution: one walk that returns each height once
One postorder walk returns the height of each subtree exactly once, and each node scores its candidate path from the two heights it just received. That one sentence is the whole method.
Postorder means a node is scored after its children. The walk keeps one shared best value. Each node compares its own candidate against that best and raises it when the candidate wins.
The one-walk solution on every case
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def diameter(root):
best = [0]
def solve(node):
if node is None:
return -1
left_height = solve(node.left)
right_height = solve(node.right)
through = left_height + right_height + 2
if through > best[0]:
best[0] = through
return 1 + max(left_height, right_height)
solve(root)
return best[0]
balanced = TreeNode(5,
TreeNode(3, TreeNode(1), TreeNode(4)),
TreeNode(8, TreeNode(7), TreeNode(9)))
chain = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
deep_left = TreeNode(10,
TreeNode(5,
TreeNode(3, TreeNode(2, TreeNode(1))),
TreeNode(8, TreeNode(9, TreeNode(11)))),
TreeNode(12))
single = TreeNode(42)
for name, tree, expected in [("balanced", balanced, 4), ("chain", chain, 3),
("deep left", deep_left, 6), ("single node", single, 0)]:
result = diameter(tree)
print(name, "->", result, "expected:", expected, "match:", result == expected)All four cases from the start of the article pass. No height is computed twice. Each height travels up one edge to its parent and is used there once.
Walkthrough: the deep left tree, scored bottom up
The walkthrough scores the deep left tree in postorder. Leaves print first. The root prints last, after both of its subtrees are known.
Each node's candidate and the best so far
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def solve_traced(node, best):
if node is None:
return -1
left_height = solve_traced(node.left, best)
right_height = solve_traced(node.right, best)
through = left_height + right_height + 2
if through > best[0]:
best[0] = through
print("node", node.value, "- left height", left_height,
"- right height", right_height, "- through", through,
"- best so far", best[0])
return 1 + max(left_height, right_height)
deep_left = TreeNode(10,
TreeNode(5,
TreeNode(3, TreeNode(2, TreeNode(1))),
TreeNode(8, TreeNode(9, TreeNode(11)))),
TreeNode(12))
best = [0]
solve_traced(deep_left, best)
print("diameter:", best[0])Node 5 scores the winning candidate of 6. Its left height is 2 and its right height is 2, so its path holds 2 plus 2 plus 2 edges. The root scores only 5 afterwards, and the best stays at 6.
The answer is read off the best value at the end. The winning path is 1, 2, 3, 5, 8, 9, 11. It sits inside the left subtree, as the first section promised.
Complexity
The brute force can rewalk a subtree for every node, so its worst-case time is O(n^2) for n nodes. The one-walk solution visits each node once, so its time is O(n).
The one-walk solution stores no lists, so its extra space is the recursion stack. The stack holds one root-to-leaf path, so its space is O(h) for height h.
Counting the work on chains of three sizes
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node, visits):
if node is None:
return -1
visits[0] += 1
return 1 + max(height(node.left, visits), height(node.right, visits))
def collect(node, nodes):
if node is None:
return
nodes.append(node)
collect(node.left, nodes)
collect(node.right, nodes)
def brute_visits(root):
nodes = []
collect(root, nodes)
visits = [0]
for node in nodes:
height(node.left, visits)
height(node.right, visits)
return visits[0]
def optimal_visits(root):
visits = [0]
def solve(node):
if node is None:
return -1
visits[0] += 1
return 1 + max(solve(node.left), solve(node.right))
solve(root)
return visits[0]
def make_chain(n):
root = None
for value in range(n, 0, -1):
root = TreeNode(value, root)
return root
for n in [4, 8, 16]:
tree = make_chain(n)
print("chain nodes", n, "- brute height visits:", brute_visits(tree),
" optimal visits:", optimal_visits(tree))The counts prove the growth claim. Doubling the chain roughly quadruples the brute force visits. The optimal visits simply double, matching the node count.
Edge cases and pitfalls
An empty tree and a single node both answer 0. Neither holds a pair of nodes with an edge between them. A two-node tree answers 1, for its one edge.
Counting nodes instead of edges is the classic mistake. A path list holds one more value than its edge count. The single node run below shows the gap at its smallest, with one node and zero edges.
Edge cases, run
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def diameter(root):
best = [0]
def solve(node):
if node is None:
return -1
left_height = solve(node.left)
right_height = solve(node.right)
through = left_height + right_height + 2
if through > best[0]:
best[0] = through
return 1 + max(left_height, right_height)
solve(root)
return best[0]
print("empty tree:", diameter(None))
print("single node:", diameter(TreeNode(42)))
print("two nodes:", diameter(TreeNode(1, TreeNode(2))))
print("left chain of four:", diameter(TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))))
print("root with one leaf:", diameter(TreeNode(5, None, TreeNode(8))))A chain answers its node count minus one. The left chain of four answers 3. Any answer equal to the node count has counted a node as an edge somewhere.
Exercise
A node has left height 2 and right height 3. How many edges has the path through that node?