# Binary Tree Longest Consecutive Sequence

I written code to solve this problem which I found on leetcode. My solution worked for the vast majority of the test cases run against it but failed on 2 for some reason. The first test case it failed on had a extremely large input size for the tree so it's really hard to determine what is actually wrong with the algorithm I wrote:

class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

def lcs(root):
if root is None:
return 0
left_lcs = lcs(root.left)
right_lcs = lcs(root.right)
if root.left is not None:
if root.left.val - root.val == 1:
if root.right is not None:
if root.right.val - root.val  ==1:
if root.right is None and root.left is None:
return 1


Are there any glaring issues with the code that I'm just missing?

• If the longest consecutive sequence is longer than the stack size (1000 by default), this will raise an exception. So in Python you might want to use an iterative approach instead of a recursive one. Aug 3, 2018 at 17:43

Recursion is probably your main problem, as Graipher mentioned in the comments.

You could refactor it to be iterative:

def lcs(root):
if root is None:
return 0
longest_sequence = 0
nodes = dict()
nodes[root] = 1
while True:
new_nodes = dict()
for node, length in nodes.items():
for subnode in (node.left, node.right):
if subnode:
if subnode.val - node.val == 1:
new_nodes[subnode] = length + 1
else:
new_nodes[subnode] = 1
longest_sequence = max(longest_sequence, length)
nodes = new_nodes
if not nodes:
break
return longest_sequence

• Ok, so you're essentially just doing a level order traversal instead of a depth first recursive solution. Do you think it would be better to just do recursive solutions in another language? Using recursive dfs was just more intuitive to me in this case. Aug 7, 2018 at 14:39