Binary Tree Longest Consecutive Sequence
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the length of the longest consecutive sequence path.
Such a path follows parent-to-child edges only (it can start at any node but never goes back up), and each value on it is exactly one more than the value before it. The length is the number of nodes on the path.
Examples
Input: root = [4,5,2,6,None,3,None,None,None,4,5] Output: 3
Both 4 -> 5 -> 6 and 2 -> 3 -> 4 have three nodes.
Input: root = [3,None,2,None,1] Output: 1
Each child is one less than its parent, so no path is longer than a single node.
Input: root = [1,None,3,2,4,None,None,None,5] Output: 3
3 -> 4 -> 5 has three nodes; 1 -> 3 breaks the run.
Constraints
- The number of nodes is in the range [1, 3 · 10^4]
- -3 · 10^4 <= Node.val <= 3 · 10^4
Approaches
- Baseline: start a search at every node — time O(n · h), space O(h)
Follow-up
If the path may also go up and then down (child to parent to other child) and may count down as well as up, each node needs the longest increasing and decreasing runs below it, combined at the turning node. How would the state change?
Related problems
Start free on Cariara · Coding problems · System design studio
