Counting Up Down the Tree

Medium

You are given the root of a binary tree holding integers. Consider paths that start at any node and only go downward, from parent to child. A path qualifies if every next node's value is exactly 1 more than the previous one, like counting 4, 5, 6, … Return the number of nodes on the longest such path. A single node is a path of length 1.

Example 1

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

On the right there is 2 → 3 → 4, on the left 5 → 6 → 7. Both have length 3 and nothing is longer.

Example 2

root=tree_node([3, 2, None, 1]) → 1

The values go down the tree, but each step must go up by one, so the best path is a single node.

Example 3

root=tree_node([1, None, 2, 4, None, 5]) → 2

Constraints

1 ≤ number of nodes ≤ 3·10⁴
-3·10⁴ ≤ Node.val ≤ 3·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, 6, 2, 7, 1, None, 3, None, None, None, None, None, 4])

Expected

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