Height and diameter of a tree in Python

Why this lesson matters

Height tells you how deep a tree is, and depth decides how fast many tree operations run. A search in a balanced tree takes about as many steps as its height, so a tree with height 10 can hold about a thousand items, while a tree with height 1,000 can be far slower to search. Diameter is a favourite interview question because it tests a skill that comes up everywhere in tree work: you must combine the answers from two subtrees into one answer for their parent.

By the end of this lesson you will write a recursive height function, a one-pass diameter function that keeps a best value outside the recursion, and a balance check that stops early. You will also see why the obvious diameter method is slow, and how to measure that slowness.

The last lesson showed you how to walk a tree. This one answers questions about the whole tree, and it uses the same walk in a new way. Each call returns a number to its parent, and the parent uses that number to build its own answer. This "answers flow upward" pattern shows up in most tree problems.

Height: a question about the children

The height of a tree is the length of the longest path from the root down to a leaf. In the last lesson we counted the height in nodes. This course keeps that rule: an empty tree has height 0, a tree with one node has height 1, and the six-node tree from the last lesson has height 3, because the path 1, 2, 4 holds three nodes.

Some books count height in edges, the lines between nodes. For the same tree that gives height 2. Both are correct, and they differ by exactly one. When a problem gives you a number to match, check which one it uses. The code in this lesson and in the practice problems uses nodes, unless the text says otherwise.

Here is the idea in plain words. Suppose you stand at a node. Your height is one more than the height of your taller subtree. You do not need to know the whole tree. You only need the height of your left subtree and the height of your right subtree, and then you add one for yourself. Each of those subtrees is a smaller tree, so you can ask the same question of them. That is a recursive definition, and it has a base case: the height of an empty tree is 0.

Think about a family where you want to know the number of generations below a grandparent. Each person asks each child, "how many generations do you have below you?" Each child answers with its own count, the grandparent takes the larger answer and adds one. The question moves down, and the answers move up. A tree works the same way, with one answer per node.

The formula

In code, the rule has two lines:

height(None) = 0
height(node) = 1 + max(height(node.left), height(node.right))

The max function picks the taller of the two subtrees, because the longest path goes down the taller side. The 1 + counts the node itself. Here is the code for height and for size, which counts all nodes. The two functions have the same structure, and comparing them is a good way to see the pattern.

Output:

height: 3
size: 6
height of empty tree: 0
height of chain: 4

The function height never asks about a whole path at once. It asks two smaller questions, one per child, and answers with one number. That is the entire design, and every tree function in this module follows it.

Tracing height on the six-node tree

Trace height(root) on the six-node tree. This trace is short, so write it out on paper as you read.

• height(1) calls height(2) and waits.
• height(2) calls height(4) and waits.
• height(4) calls height(None) for its left child. That returns 0. It calls height(None) for its right child, which also returns 0. The maximum of 0 and 0 is 0, so height(4) returns 1 + 0, which is 1.
• Back in height(2), the left answer is 1. It calls height(5), and 5 is a leaf, so it returns 1. The maximum of 1 and 1 is 1, so height(2) returns 2.
• Back in height(1), the left answer is 2. It calls height(3). Node 3 has no left child, so height(None) returns 0. Its right child 6 returns 1. So height(3) returns 1 + max(0, 1), which is 2.
• Now height(1) has 2 from the left and 2 from the right. It returns 1 + max(2, 2), which is 3.

The picture to keep in mind is the six-node tree with a number written beside each node: the height its subtree returns. The leaves show 1, node 2 and node 3 show 2, and the root shows 3. The numbers move up the tree, one level at a time.

The call stack for the same calls grows down the left branch and shrinks as the answers return, the same way as in the first lesson.

Complexity of height and size

Each function visits every node once, and each call does a fixed amount of work: two recursive calls and a comparison. So the time is O(n). The None calls are also visited, but there are only about n + 1 of them, so the total stays proportional to n.

The space is the call stack. At any moment the stack holds one frame per node on the current path from the root, so the peak is O(h), where h is the height. For a balanced tree with a million nodes, the height is about 20, so the stack stays tiny. For a chain with a million nodes, the stack needs a million frames and Python stops the program with a RecursionError. The next sections show that limit in practice. Keep it in mind for every recursive tree function.

Diameter: the longest path, which may not touch the root

The diameter of a tree is the number of edges on the longest path between any two nodes. That path does not have to pass through the root. It can run down one side of the tree, across a node and then down the other side, and that node may be far from the root.

Here is the six-node tree again:

        1
       / \
      2   3
     / \   \
    4   5   6

The path from 4 up to 2, up to 1, down to 3, and down to 6 has four edges. It goes through the root. The path from 4 to 5 has two edges and stays under node 2. The longest path overall is 4, so the diameter is 4.

Now picture a different tree. The root has a left child 2, and node 2 has a long chain of children going down on the left. The root's right child is a single leaf. The longest path may run from the bottom of the long chain up to 2 and across to the root, without touching the right leaf at all. The longest path does not always go through the root.

The key idea: the path bends at one node

Every path between two nodes has a highest point. Call it the top of the path. The top is the node closest to the root. From the top, the path goes down the left side and down the right side, and it may use only one side. So for every node, the longest path that bends at that node has a length of its left height plus its right height. The number of edges from the node down the left branch equals height(node.left), because a branch of k nodes has k edges counting the edge from the node to its child. The same holds for the right side.

So the diameter is the largest of height(node.left) + height(node.right) over all nodes. The six-node tree's longest path bends at node 1, with the left height 2 and the right height 2, which gives 4.

The slow way

The first method that comes to mind is to compute the path through every node and take the largest. It needs the height of each subtree, so it calls height at every node.

def diameter_slow(node):
    if node is None:
        return 0
    through = height(node.left) + height(node.right)
    left = diameter_slow(node.left)
    right = diameter_slow(node.right)
    return max(through, left, right)

This is correct. Its cost is the problem. Each call to height walks its whole subtree again, so the same nodes are visited many times. On a balanced tree the total work is O(n log n), which is acceptable. On a chain of n nodes, the node at the top calls height on a subtree of size n - 1, the next node calls it on n - 2, and so on. The total is about n squared divided by two. For a chain of 10,000 nodes that is about 50 million visits. Python would also stop that chain with a RecursionError before the count finished, so the count shows the cost, not a run you can do. For a chain of a million nodes it is about half a trillion, which is far too slow in any language.

The fast method avoids the repeated walks. It computes the height and the path through each node in the same recursion, so every node is visited once.

The fast way: return one value, record another

The trick is that the recursive function has two jobs and needs two outputs. It must return the height to its parent, because the parent needs it. It must also record the best diameter seen so far, because the answer can come from any node. The function returns the height, and it keeps the best diameter in a variable that belongs to the outer function.

Python gives you a clean way to do this with a nested function. A function defined inside another function can read the outer variables. To change one of them, it declares the name with nonlocal. Without that line, an assignment inside the nested function would create a new local variable and leave the outer one alone.

Output:

six-node tree: 4
chain of 4: 3
chain of 1: 0
empty tree: 0

The helper chain_of builds a left chain. It starts from the last value and works upward, so each new node becomes the head and points its left at the previous head. It is a short way to make the chains used in the tests.

Each call to diameter creates a new best variable, so two calls in a row cannot affect each other. This avoids a bug that appears in many programs, which the common mistakes section shows.

Reading the function line by line

• lh = height_and_record(node.left) gets the height of the left subtree. The call also records every diameter inside the left subtree, because the function updates best as it goes.
• rh = height_and_record(node.right) does the same on the right.
• best = max(best, lh + rh) checks the path that bends at this node. Its length is the left height plus the right height. If that beats the best so far, it becomes the new best.
• return 1 + max(lh, rh) returns the height to the parent, which is one more than the taller side.

The function runs once per node, so the time is O(n). The space is the call stack, O(h), just like the height function.

Trace on the six-node tree

Each line of the next program shows the node, the two heights from its children, the height it returns, and the path that bends at it. The printing is the only change from the function above.

Output:

node 4: left 0, right 0, height 1, path bending here 0
node 5: left 0, right 0, height 1, path bending here 0
node 2: left 1, right 1, height 2, path bending here 2
node 6: left 0, right 0, height 1, path bending here 0
node 3: left 0, right 1, height 2, path bending here 1
node 1: left 2, right 2, height 3, path bending here 4
diameter: 4

Read the output from top to bottom. Node 2 has two leaves below it, so its path bends there with length 2. Node 3 has only a right child, so its left height is 0 and its path is 1. Node 1 has heights 2 and 2 from its children, so its path has length 4, which is the largest value. The final best is 4.

The trace is the best way to check the code on a tree you are unsure about. Print the four numbers at each node and compare them with what you expect by hand.

Worked example: a path that bends below the root

The one-pass method is easy to get wrong when the longest path does not pass through the root. Tree M is a good test. It has nine nodes, and its root has one short side and one long side.

            1
           / \
          2   9
         / \
        3   6
       /     \
      4       7
     /         \
    5           8

Before you read the trace, make a prediction. The left side of the root holds a long branch, and the right side holds only node 9. A quick look suggests the longest path goes from the bottom of the left branch up to node 1 and down to 9. Check that guess against the trace.

The trace is the same function as in the trace section, with tree M built in the program instead of the six-node tree. Each line shows one node after its children have been handled, in postorder. Its output is:

node 5: left 0, right 0, height 1, path bending here 0
node 4: left 1, right 0, height 2, path bending here 1
node 3: left 2, right 0, height 3, path bending here 2
node 8: left 0, right 0, height 1, path bending here 0
node 7: left 0, right 1, height 2, path bending here 1
node 6: left 0, right 2, height 3, path bending here 2
node 2: left 3, right 3, height 4, path bending here 6
node 9: left 0, right 0, height 1, path bending here 0
node 1: left 4, right 1, height 5, path bending here 5
diameter: 6

The guess was wrong. Node 2 is where the longest path bends. Its left side has height 3, from 3, 4 and 5, and its right side also has height 3, from 6, 7 and 8. The path through node 2 has 3 + 3 = 6 edges, along the nodes 5, 4, 3, 2, 6, 7, 8. At the root, the left height is 4 and the right height is 1, so the path through the root has only 4 + 1 = 5 edges. The answer is 6.

Read the column called "path bending here" from top to bottom. The largest value is 6, and it appears on the line for node 2. The function does not need to know where the path is. It records the best value at every node, so the node that holds the answer is found by the comparison, not by a guess.

A function that only checked the root would print 5 for this tree, and that answer is wrong by one edge. This is why the one-pass method checks every node, not only the top one.

When recursion runs out of room

Every recursive call takes a frame on the call stack, and Python limits how deep that stack can grow. The limit is the recursion limit from the first lesson, which is 1000 by default. For most trees this limit is never reached. A balanced tree of a million nodes is only about 20 levels deep. A chain is different, because its height equals its number of nodes. A recursive walk of a chain of 2,000 nodes needs 2,000 frames at once, which is more than the default limit allows.

The program below builds a chain of 100,000 nodes and measures its height in two ways. The iterative version keeps its own stack of nodes and depths in a list, which lives in memory managed by Python and can hold as many items as there is room for. The recursive version uses the call stack, and it fails.

Output:

iterative height: 100000
recursive height: RecursionError

The try and except lines let the program keep running after the error, so both answers print. In a real program you would not hide this error. You would change the design, so that a very deep input uses the iterative walk. The depth that is safe depends on the Python version and on how much of the stack the program already uses. Do not rely on any particular number. If the input may be a long chain, write the walk without recursion.

The iterative version pushes each node together with its depth, pops one pair at a time, and records the largest depth it sees. The pair (node, depth) is a tuple, which is a fixed group of values. For a chain the list never holds more than one pending node, so it stays tiny. For a bushy tree the list can hold many nodes, but it is still bounded by the number of nodes, which is O(n), and it does not depend on the recursion limit.

Balanced trees

A tree is balanced when, at every node, the heights of the left and right subtrees differ by at most 1. Balanced trees keep their height small, and that is why search trees try to stay balanced. A simple version of the check calls height at every node. That repeats the slow work from the diameter section. A better version computes heights from the bottom up and stops as soon as it finds an unbalanced node.

The trick is to return a special value, -1, to mean "this subtree is unbalanced". Any height is zero or more, so -1 can never be a real height. When a child returns -1, the parent returns -1 at once without checking anything else.

Output:

six-node tree: True
lopsided chain of 3: False
empty tree: True

In the lopsided tree, node 1 has a left subtree of height 2 and an empty right subtree of height 0. The difference is 2, which is more than 1, so the check returns -1 at node 1, and is_balanced reports False. The six-node tree passes every check, since its subtrees at node 1 have heights 2 and 2, and at node 2 they have heights 1 and 1.

The method still visits every node in the worst case, so the time is O(n). The gain is that it never does repeated work, and it stops early on a bad tree. Notice that check_height returns two things in one number. A positive number is a height, and -1 is a warning. Encoding a second meaning in a special value is a common pattern, and you must document it clearly in your code. In a larger project you might return a tuple (ok, height) instead, which says each meaning in its own name.

Edge cases you must test

Most height and diameter bugs show up only on small or odd trees. Test these every time.

• Empty tree: height 0, diameter 0, and balanced. The None base case must return these values.
• Single node: height 1, diameter 0. The diameter is 0 edges, because a path between one node and itself has no edges.
• Chain: height equals the number of nodes, and the diameter equals the number of nodes minus 1. A chain of 4 has diameter 3.
• Perfect tree: the diameter goes through the root, and the height is the number of levels. A perfect tree of height 3 has diameter 4.
• Longest path away from the root: as described above, make sure your function still finds it when the root has a short side and a long side deeper down.

Testing a tree function before you trust it

A tree function can look right and still fail on a shape you did not picture. The habit that prevents this is to write a small set of test trees, predict the answer for each one on paper, and only then run the code. Four trees cover most of the risk. The empty tree tests the base case. A single node tests the smallest non-empty case. A chain tests the deep path, where height and diameter differ in an important way. A bushy tree such as the six-node tree tests the case where the answer passes through the root.

Write the predictions first. For the six-node tree, the height is 3, the size is 6 and the diameter is 4. For a chain of 4, the height is 4 and the diameter is 3. For a single node, the height is 1 and the diameter is 0. For the empty tree, both are 0. If your code disagrees with a prediction, the difference tells you what is wrong. A height that is one too big usually means a missing base case or a + 1 in the wrong place. A diameter that is one too big usually means a node was counted as an edge.

Tests also protect you from the shared-state bug. Run the diameter function on a chain, then on a single node, in the same program. The second answer must be 0. If it is not, the code keeps state between calls. This two-call test takes a minute to write and catches a mistake that is hard to see by reading the code.

Common mistakes and what they look like

A function that forgets to return

In Java, the compiler refuses a method that can end without a return. Python does not check this. A function with no return at the end gives back None, and the error appears later, in the parent that tries to use that value. Here is a height function with the return left off its formula line. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def height(node):
    if node is None:
        return 0
    1 + max(height(node.left), height(node.right))
 
 
root = TreeNode(1)
root.left = TreeNode(2)
print(height(root))

The output is:

Traceback (most recent call last):
  File "main.py", line 16, in <module>
    print(height(root))
          ~~~~~~^^^^^^
  File "main.py", line 11, in height
    1 + max(height(node.left), height(node.right))
        ~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: '>' not supported between instances of 'int' and 'NoneType'

Read the last line. The call on node 2 finds that node 2 is a leaf. Its formula line computes 1 + max(0, 0), which is 1, but it does not return that value. So node 2 gives back None. Then the call on node 1 passes that None to max together with 0 from the empty right child, and max compares them with > and fails. The fix is to write return 1 + max(...). Check the return on every path, and test a small tree before you trust the function.

Returning the diameter where the parent needs the height

If the recursive function returns best instead of 1 + max(lh, rh), the parent receives the wrong number and the answers are wrong. Test the return value on a small tree, using the trace from this lesson, and check that each node returns its height.

Mixing nodes and edges

The formula lh + rh gives the number of edges on the path. The height is in nodes. If your height function counts edges instead, the path formula changes. Stay with one unit for the whole program. This course uses nodes for height, so height(None) is 0 and height(leaf) is 1, and the path through a node adds the two child heights as they are.

Keeping the best value in a module-level variable

A nonlocal variable belongs to one call of diameter, so each call starts fresh. A variable at the top of the file belongs to the whole program. It keeps its old value between calls. Suppose you keep best at the top of the file and only set it once. Here is what happens when you call the function twice.

Output:

first call: 3
second call on one node: 3

The second answer should be 0, because a single node has no edges. The 3 came from the first call and was never cleared. The fix is to set best = 0 at the start of diameter_without_reset with global best, or, as the working version above does, to keep best inside the function with nonlocal. Either way, each call starts from a known value.

Calling height twice on the same child

It is easy to call height(node.left) in the diameter code and then call the recursive function again on the same child. That doubles the work at each level. The fast method calls its children once, saves the results in lh and rh, and uses those values twice. Store results in variables, not in new calls.

Debugging walkthrough: a wrong answer on a chain

Suppose a tree of 5 nodes in a left chain gives a diameter of 5, and you expected 4. Start with the definition. A chain of 5 nodes has 4 edges between them, so 5 is too big by one. The most likely cause is that the code adds 1 somewhere, or uses the height in nodes where the edges were needed.

Add a trace like the one in this lesson. Print the left height, the right height and the path at each node. On a left chain, each node has a right height of 0, so the path at each node equals its left height. The top node should show a path of 4, and the leaf should show 0. If the top node shows 5, the path formula is using a height that counts the node itself twice. Check whether you wrote 1 + lh + rh instead of lh + rh. That extra 1 is the bug.

Once the trace shows the right values, remove the print statements and run the program again on the same tree, to confirm the fix.

Real-world uses

Height and depth appear in many places outside interview problems. A file system's folder depth decides how long a file path can get, and a program that walks folders must not overflow its call stack on a deeply nested tree. A JSON document is a tree, and a parser that limits nesting depth protects the program from a document designed to exhaust memory. A computer network with routers has a diameter: the largest number of hops between any two machines, which tells engineers how many steps a message might take. A balanced tree keeps its height at about log n, which is why databases use balanced trees for their indexes. A search that visits about 20 nodes can find one row among a million.

Each of these uses asks one of the questions in this lesson: how deep is it, how far apart are the two farthest points, or is it evenly shaped.

Interview-style questions

Find the height of a tree. The base case is None, which returns 0. The answer is one more than the taller child. O(n) time and O(h) space.

Find the diameter in one pass. Return the height from each call, and record lh + rh at each node in a variable. Keep that variable inside the function, or reset it before each run. O(n) time and O(h) space.

Is the tree balanced? Return the height from each call, with -1 for unbalanced. Stop early when a child returns -1. O(n) time.

Why is the naive diameter O(n squared) on a chain? Each node calls height on its whole subtree, and the subtrees shrink by one each time. The sizes add up to about n squared over two.

What if the tree is huge and deep? Recursion uses one frame per level, so a chain of a million nodes can exceed Python's recursion limit. An iterative version uses a list as an explicit stack, which can hold the same nodes without the recursion limit. The idea is the same as the iterative inorder in the first lesson.

Practice

Try each exercise yourself before you open the answer. Use paper to predict the answer, then run the code to check.

1. Write def count_leaves(node):. Predict its answer for the six-node tree before you run it. Hint: both children are None.

Show the answer

def count_leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return count_leaves(node.left) + count_leaves(node.right)

On the six-node tree the answer is 3, the leaves 4, 5 and 6. The function returns 0 for a missing child and 1 only for a node with both children missing.

2. Predict the height and diameter of a tree with root 1, a left child 2, and node 2 having a right child 3. Then write the code to confirm your answer. Hint: count the nodes on the path, and count the edges separately.

Show the answer

The tree is 1, with left child 2, and 2 has right child 3. The path from 1 to 3 has three nodes, so the height is 3 in nodes. The diameter is the longest path in edges, which is 2, the path 1, 2, 3. Count the edges between the nodes, not the nodes themselves, for the diameter.

3. Write def is_perfect(node): that returns True when every level is full. Test it on the six-node tree (False) and on a tree of 7 nodes with all levels full (True). Hint: compare the height with the size. A perfect tree of height h has 2 ** h - 1 nodes.

Show the answer

def is_perfect(node):
    h = height(node)
    return size(node) == 2 ** h - 1

The height and size functions come from the first code block in this lesson. For the six-node tree, the height is 3 and the size is 6, but a perfect tree of height 3 has 7 nodes, so the answer is False. An empty tree has height 0 and size 0, and 2 ** 0 - 1 is 0, so it correctly counts as perfect.

4. Write def min_depth(node): that returns the number of nodes on the shortest path from the root to any leaf. Predict the answer for the six-node tree. Hint: a node with one child should not count as a leaf, so handle the case where one child is None separately.

Show the answer

def min_depth(node):
    if node is None:
        return 0
    if node.left is None:
        return 1 + min_depth(node.right)
    if node.right is None:
        return 1 + min_depth(node.left)
    return 1 + min(min_depth(node.left), min_depth(node.right))

For the six-node tree the answer is 3, because all three leaves 4, 5 and 6 are three nodes deep counting the root. The special cases matter: node 3 has only one child, and a plain min would treat its missing left side as depth 0 and return 2.

5. Change diameter_slow so that it returns the diameter in nodes, not edges. Predict the change to the answer for the chain of 4.

Show the answer

Return diameter_slow(root) + 1 for any non-empty tree, because a path with k edges has k + 1 nodes. For the chain of 4 the diameter in edges is 3, so in nodes it is 4. An empty tree must still return 0, so keep the check for None and return 0 there before adding one.

6. Write a function that returns the value of the deepest node. If several nodes share the greatest depth, return the first one met in the walk from left to right. Test it on the six-node tree.

Show the answer

def deepest_value(node):
    best_val = None
    best_depth = 0
 
    def walk(n, depth):
        nonlocal best_val, best_depth
        if n is None:
            return
        if depth > best_depth:
            best_val = n.val
            best_depth = depth
        walk(n.left, depth + 1)
        walk(n.right, depth + 1)
 
    walk(node, 1)
    return best_val

The test is strict (>), so the first node met at the greatest depth wins. On the six-node tree the walk meets 4 at depth 3 before 5 and 6, so the function returns 4.

7. Write def sum_of_diameters(node): that adds the path length bending at every node. Predict the total for the six-node tree. Hint: add up the path values from the trace in this lesson.

Show the answer

The path values at the six nodes are 0, 0, 2, 0, 1 and 4, which add up to 7, as the trace in this lesson shows. One walk can add them up like this:

def sum_of_diameters(node):
    total = 0
 
    def walk(n):
        nonlocal total
        if n is None:
            return 0
        lh = walk(n.left)
        rh = walk(n.right)
        total += lh + rh
        return 1 + max(lh, rh)
 
    walk(node)
    return total

8. Explain why check_height returns -1 at node 1 of the lopsided chain, and why node 2 still returns a height. Then describe what would change if node 1 had a right child with a subtree of height 3, and its left child returned -1.

Show the answer

Node 1 asks its left child first. Node 2 is fine: its left child has height 1 and its right side is empty, so the difference is 1 and node 2 returns 2. Node 1 then asks its right side, which is empty and returns 0. The left height is 2 and the right height is 0, so the difference is 2, and node 1 returns -1.

If the left child returned -1, node 1 would return -1 straight away and never ask its right child. That is the early exit. It saves work only when a bad subtree is found early, so the gain depends on the shape of the tree.

9. Write an iterative version of height that uses a list as a stack of nodes and a second list as a stack of depths. Test it on the chain of 4, which should return 4.

Show the answer

Use one list that holds (node, depth) pairs, as in height_iterative in this lesson. A second list is not needed in Python, because a tuple holds both values together. Two parallel lists also work, if you push and pop both in the same order. The chain of 4 returns 4.

10. Write a program that reads a tree with the same input format as the first lesson, then prints its height and whether it is balanced. Use the input 7 and 1 2 3 4 5 null 6. Expected output: height: 3 and balanced: True.

Show the answer

Use the builder from the first lesson, which reads the number n and then the tokens. Compute the height with height and check the balance with is_balanced, and print both. The printed lines are height: 3 and balanced: True. The six-node tree is balanced because every node's two subtrees differ by at most one in height.

11. The diameter of a tree is 6, and its height is 4. Give an example of a tree that has these values, and say which node the longest path bends at.

Show the answer

Use a root with two chains of three nodes hanging from it, one on the left and one on the right. The root is 1, the left chain is 2, 3, 4 going left, and the right chain is 5, 6, 7 going right. The height is 4 nodes, from the root down a chain. The longest path runs from the bottom of the left chain up to the root and down the right chain, with 3 edges on each side, so the diameter is 6. The path bends at the root. Check the numbers with the trace function from this lesson.

12. Write def diameter_with_holder(node, best): that keeps the best value in a list with one item instead of a nonlocal variable. Explain why this avoids the shared-state bug, and test two calls in a row on different trees.

Show the answer

def diameter_with_holder(node, best):
    if node is None:
        return 0
    lh = diameter_with_holder(node.left, best)
    rh = diameter_with_holder(node.right, best)
    best[0] = max(best[0], lh + rh)
    return 1 + max(lh, rh)

Call it with best = [0] for each tree, and read best[0] at the end. Create a new list for each tree, so the second tree does not inherit the first answer. A list is passed by reference, so the function can change the item that the caller sees. This is the same idea as the holder object in other languages: the state lives with the call, not with the module.

What you now know

• Height is one more than the taller subtree, with None returning 0. This course counts height in nodes.
• A recursive function returns the answer for its subtree, and the parent combines the answers from its two children.
• The diameter is the largest left height + right height over all nodes. The path can bend at any node, not only the root.
• The slow diameter calls height at every node and takes O(n squared) on a chain. The one-pass method returns the height and records the path in a separate variable, which takes O(n).
• Python's default recursion limit is 1000, so a very deep tree needs an iterative walk.
• A balance check can return -1 to signal an unbalanced subtree and stop early.
• Keep a best value inside one call with nonlocal, or pass it in as a holder, so that each call starts fresh.