Find the Longest Link Between Any Two Nodes
Solve this ProblemYou are given the root of a binary tree. Return the length of the longest path between any two nodes in the tree, counted in connections (edges) rather than nodes. The path may pass through the root, but it does not have to.
The longest path that bends at a given node uses the taller branch on each side of it. Working out the heights once, from the bottom up, and updating a running best at every node avoids recomputing them.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 (the values never affect the answer) - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
A link between two nodes is the unique path that joins them through parent-child connections; its length is the number of connections (edges) on it. The path may pass through any node, not necessarily the root. Return the length of the longest such path (0 for an empty or single-node tree)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — At Each Node, Measure Both Sides From Scratch
BruteThe longest link has a highest node (where it bends, or its endpoint). Through such a node the best link is (height of its left subtree) + (height of its right subtree), in edges. So for every node, compute that sum with a separate height function, and take the largest over all nodes (recursing into the left and right children). Correct — but the height function re-walks an entire subtree each time, and it is called again at every node below, so the work adds up to O(n²) on a tall tree.
O(n²)O(h)1class Solution {
2 public int longestLink(TreeNode root) {
3 if (root == null) return 0;
4 int through = height(root.left) + height(root.right);
5 return Math.max(through, Math.max(longestLink(root.left), longestLink(root.right)));
6 }
7
8 private int height(TreeNode node) {
9 if (node == null) return 0;
10 return 1 + Math.max(height(node.left), height(node.right));
11 }
12}Optimal — One Pass: Update the Best While Returning Heights
OptimalCompute heights bottom-up (height = 1 + the taller side, 0 for an empty subtree), and use the two child heights that are already in hand. At each node, the longest link that bends at this node is left + right (edges), so update a running best with it; then return the node's own height for its parent. Every node does O(1) work with values it just received, so the whole tree costs O(n) with O(h) recursion space — no height is ever recomputed.
O(n)O(h)1class Solution {
2 private int best;
3
4 public int longestLink(TreeNode root) {
5 best = 0;
6 depth(root);
7 return best;
8 }
9
10 private int depth(TreeNode node) {
11 if (node == null) return 0;
12 int left = depth(node.left);
13 int right = depth(node.right);
14 best = Math.max(best, left + right);
15 return 1 + Math.max(left, right);
16 }
17}