InternDoor

Nodes no ancestor outranks

Mediumtrees · depth-first search

Reported in interviews at (where)

A node of a binary tree is good when no node on the path from the root down to it holds a larger value. The root is always good, and a value equal to the largest one above it still counts.

Return how many good nodes the tree has.

Example 1
Input
root = [5,3,7,6,2,null,7]
Output
4

5, 6 and both 7s are good; 3 and 2 have 5 above them.

Example 2
Input
root = [-1,-1,null,-2,0]
Output
3

The second -1 equals the root, so it is good; -2 is not, and 0 is.

Limits

  • 1 <= number of nodes <= 20000
  • -10000 <= Node.val <= 10000
  • the tree is at most 3000 levels deep

Hints

Hint 1

Walk down the tree carrying the largest value seen on the way. A node is good when it is at least that large.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.