How do you find the diameter of a binary tree?
The diameter is the longest path between any two nodes. You work out the height of every node and you keep the biggest path that you find on the way back up.
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 depth(node):
nonlocal best
if node is None:
return 0
left = depth(node.left)
right = depth(node.right)
# The path that goes through this node.
path = left + right
if path > best:
best = path
# The height of this node.
return 1 + max(left, right)
depth(root)
return best
So how does it work? The helper function gives back the height of a sub-tree, which is the number of nodes on the longest path from that node down to a leaf. At each node you get the height of the left side and the height of the right side.
And then there are two paths to think about at that node. The path that goes down the left side and comes back up the right side has a length of left plus right. That is a path through the node. And the path that goes down the tallest side is the height of the node, which is one plus the bigger of the two.
the tree 8
/ \
3 10
/ \ \
1 6 14
the heights going up
the node 1 1
the node 6 1
the node 3 2, and the path through it is 1 + 1 = 2
the node 14 1
the node 10 2, and the path through it is 1 + 1 = 2
the node 8 3, and the path through it is 2 + 2 = 4
the diameter is 4, which is the path from the 1 to the 14
And the subtlety is that the diameter does not have to go through the root. The tree above has a diameter of four, and it does pass through the root, but a tree where one side is much taller than the other has its longest path inside the tall side. That is why the code keeps the best answer as it goes and does not just work it out at the root.
And the complexity is O of n for the time, because every node is visited once, and O of h for the space.
So the rule to remember is this. At every node the path through it is the left height plus the right height, and the biggest of those is the diameter.
The next two questions in this topic show the two depths and the version that returns the path.