Card 06/ 08
Returning the Path Through a Node as Its Height
The bent path through a node is right to record and wrong to return: a parent adds it to another branch and reports a path that cannot exist.
A call that finds the longest path must return only a path its parent can extend, which is one branch down, never the path that bends through it. The two are computed side by side, from the same two heights, and the mistake is returning the one that should only be recorded. The tree 40, with children 25 and 58, where 25 has children 12 and 33, has a longest path of 3 edges, from 12 or 33 up through 25 and 40 to 58.
The two listings differ in one line, the return.
Returning the bent path against returning the height
class Node:
def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
self.value = value
self.left = left
self.right = right
def longest_path(root: Node | None) -> int:
best = 0
def walk(node: Node | None) -> int:
nonlocal best
if node is None:
return -1
left = walk(node.left)
right = walk(node.right)
best = max(best, left + right + 2)
return left + right + 2
walk(root)
return best
tree = Node(40, Node(25, Node(12), Node(33)), Node(58))
print("longest path:", longest_path(tree))longest path: 4class Node:
def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
self.value = value
self.left = left
self.right = right
def longest_path(root: Node | None) -> int:
best = 0
def walk(node: Node | None) -> int:
nonlocal best
if node is None:
return -1
left = walk(node.left)
right = walk(node.right)
best = max(best, left + right + 2)
return max(left, right) + 1
walk(root)
return best
tree = Node(40, Node(25, Node(12), Node(33)), Node(58))
print("longest path:", longest_path(tree))longest path: 3The notes give what each version's calls return, from the run.
40, height version returns 2; bent version returns 4
25, height version returns 1; bent version returns 2
12, both return 0
33, both return 0
58, both return 0
The bent version reports 4. At 25 it returns the path 12, 25, 33, two edges; the root adds that to its own right branch as though it were one line down, and records a path that would visit 25 twice. On a leaf the two values agree, so small tests pass, and the error appears only once a node with two children sits below another. The rule: what goes up must be a path the parent can extend, so it takes one branch, the longer; the path bending through a node is recorded and never returned.
← → move through sections and cards