Nearby Leaf Pairs

Medium

You are given the root of a binary tree and an integer limit. A leaf is a node with no children. The distance between two nodes is the number of edges on the unique path between them. Count the unordered pairs of distinct leaves whose distance is at most limit.

Example 1

root=tree_node([5, 8, 2, 4, None, 9, 1]), limit=3 → 1

The leaves are 4, 9 and 1. The path between 9 and 1 has 2 edges, while 4 is 4 edges away from both 9 and 1. One pair qualifies.

Example 2

root=tree_node([5, 8, 2, 4, None, 9, 1]), limit=4 → 3

The same tree, but now paths of up to 4 edges are allowed, so all three pairs of leaves qualify.

Example 3

root=tree_node([7]), limit=1 → 0

Constraints

1 ≤ number of nodes ≤ 2¹⁴
1 ≤ Node.val ≤ 100
1 ≤ limit ≤ 10

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

root=tree_node([5, 8, 2, 4, None, 9, 1]), limit=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.