Nodes That Outrank Their Subtree

Hard

You are given the root of a binary tree and an integer need. Call a node strong if its subtree (the node itself together with all of its descendants) contains at least need nodes whose value is strictly smaller than the node's own value. Return the number of strong nodes in the tree.

Example 1

root=tree_node([8, 3, 9, 1, 5]), need=2 → 1

Below the root 8 are 3, 9, 1 and 5, and three of them are smaller than 8, so it counts. Node 3 has 1 and 5 below it, and only 1 is smaller: not enough. Node 9 has nothing below it. The answer is 1.

Example 2

root=tree_node([6, 4, 2, 1, 3, 1]), need=1 → 3

6 counts (everything below it is smaller), so does 4 (it has 1 and 3 below) and 2 (it has 1 below). Leaves never count: their subtree has no other nodes. The answer is 3.

Example 3

root=tree_node([2, 2, 2]), need=1 → 0

All values are equal and the comparison is strict, so the answer is 0.

Constraints

1 ≤ number of nodes ≤ 10⁵
-10⁴ ≤ Node.val ≤ 10⁴
1 ≤ need ≤ 10

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Divide and Conquer Binary Tree

Similar problems

Rebalance a Search Tree Medium Heaviest Path in a Tree Hard K Keys Nearest to a Target Hard Fewest Guards on a Tree Hard Tree Columns With Ties Hard

Input

root=tree_node([8, 3, 9, 1, 5]), need=2

Expected

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