LC: Binary Tree Longest Consecutive Sequence - spiralgo/algorithms GitHub Wiki

Binary Tree Longest Consecutive Sequence

The Essence:

The intuition is pretty simple. If a node has a consecutive sequence (hereinafter cs) with the left branch and another on the right, the length of the cs at this node would have been the maximum of these two cs. If there is no consecutiveness with either left or right, we can assume than the length of the cs incoming from that direction is 0. If both are 0, the length of cs at this node can remain 1, only the parent.

One can think this backwards too. If a node's value is consecutive to its parent's, then it should return the length of its cs, otherwise 0. With this, less computation can be done at the level of the root.

Details:

The algorithm described here can be implemented recursively:

At the base case of null leaves, they should return a length of 0. For this, the parent sends the parent's value to a DFS of both left and right branches, and receives their values and add 1 to the maximum one. If the length of cs here is longer than the global maximum, the procedure updates it. The traversal here can be described as "post-order", i.e. "left-right-parent".