Where it runs
1. The problem
Take the two nodes of a tree that are farthest apart. How many steps are between them? In an org chart, these are the two employees whose path to each other goes through the most levels of bosses. In a network laid out as a tree, it is the largest number of hops between two computers. This largest distance is called the diameter.
The difficulty is that the longest path often doesn't go through the root. It can climb one branch up to a node somewhere in the middle of the tree, turn there, and go down another branch.
First a simple warmup on the same tree: how many leaves does it have, that is, nodes with no children? In a folder tree the leaves are the files; in an org chart they are the employees with nobody reporting to them.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Tree problems where the best path can bend at any node, not only at the root. A helper returns one value to the parent, such as height, and updates the best answer for the whole tree on the side.
The lesson's diameter under the same name, counted in edges.
countLeaves that also checks whether the leaf hangs on the left and adds its value.
The diameter helper, except a child's height counts only when the child has the same value.
The same shape with sums instead of heights, and a negative branch is dropped by taking max with 0.