Record Nodes on the Path

Medium

You get a binary tree with root root. Call a node a **record** if no node on the path from the root down to it (the node itself included) holds a larger value. Return the number of record nodes. The root is always a record.

Example 1

root=tree_node([5, 7, 2, 6, None, 8]) → 3

The root 5 always counts. 7 (path 5→7) is a record. 6 (path 5→7→6) is not, 7 is above it. 2 is not. 8 (path 5→2→8) is a record. Total 3.

Example 2

root=tree_node([4, 4, None, 4]) → 3

Equal values do not get in the way: all three nodes are records.

Example 3

root=tree_node([-3]) → 1

Constraints

the tree has between 1 and 10⁵ nodes
-10⁴ ≤ node value ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Similar problems

The Tree Seen From the Right Medium Tree Columns, Top Down Medium First Value on the Lowest Row Medium Largest Value on Each Tree Level Medium Insert a Tree Level Medium

Input

root=tree_node([5, 7, 2, 6, None, 8])

Expected

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