# Simple Recursive DFS without global variable

• ``````public class Solution {
public int longestConsecutive(TreeNode root) {
return (root==null)?0:Math.max(dfs(root.left, 1, root.val), dfs(root.right, 1, root.val));
}

public int dfs(TreeNode root, int count, int val){
if(root==null) return count;
count = (root.val - val == 1)?count+1:1;
int left = dfs(root.left, count, root.val);
int right = dfs(root.right, count, root.val);
return Math.max(Math.max(left, right), count);
}
}``````

• Nice work! Avoided using global variable.

• Can you please explain why not use global variables? Thanks!

• @chuR maybe that means if you want to examine another tree root, you should initialize a new object of class Solution. Because a global var max would influence this.

• @Jrui well, you can actually reset the global variable before return. I think this problem is perfect to use instance variable.

int tmp = this.max;
this.max = 0;
return tmp;

• My another approach is to take max of the length till now and the max of left and right length. Following is the simple implementation :

``````public int longestConsecutive(TreeNode root) {
if(root == null)
return 0;
return longestConsecutive(root, null, 0);
}
public int longestConsecutive(TreeNode root, TreeNode prev, int len) {
if(root == null)
return len; // reached the leaf node.

int leftLen = 0, rightLen = 0;
if(prev != null && root.val == prev.val + 1) { // Increasing node found
leftLen = longestConsecutive(root.left, root, len + 1);
rightLen = longestConsecutive(root.right, root, len + 1);
}
else { // This node breaks the increasing property. So start again from here.
leftLen = Math.max(len, longestConsecutive(root.left, root, 1));
rightLen = Math.max(len, longestConsecutive(root.right, root, 1));
}

return Math.max(leftLen, rightLen);

}
``````

• Same idea. My python code.

``````class Solution(object):
def longestConsecutive(self, root):

def _dfs(node, parent, cur_l):
if not node:
return cur_l
if parent == None or node.val != parent + 1:
cur_l = 0
cur_l += 1
return max(_dfs(node.left, node.val, cur_l), _dfs(node.right, node.val, cur_l), cur_l)

return _dfs(root, None, 0)
``````

• Similar idea but there is no need to separate the recursion for left and right nodes in the main function

``````public int longestConsecutive(TreeNode root)
{
if(root == null)    return 0;
int res = dfs(root, 1, root.val);
return res;
}
private int dfs(TreeNode node, int count, int prev)
{
if(node == null)    return count;
if(node.val == prev + 1)    count ++;
else    count = 1;
int left = dfs(node.left, count, node.val);
int right = dfs(node.right, count, node.val);
return Math.max(Math.max(left,right), count);
}
``````

• @Anylnb I really like your solution, its clean and simple. Keep it up.
I came up with this solution. Here I am passing the currentCount and the maxCount at each step.

``````
public int longestConsecutive(TreeNode root){
return helper(root, null, 0, 0);
}

private int helper(TreeNode root, TreeNode prev, int cnt, int mx){
if (null == root){
return Math.max(cnt, mx);
}

if (null != prev && root.val - 1 == prev.val) {
cnt++;
}else {
mx = Math.max(cnt, mx);
cnt = 1;
}

int left = helper(root.left, root, cnt, mx);
int right = helper(root.right, root, cnt, mx);

return Math.max(left, right);
}

``````

• In the main function, you do not need to call dfs() to both left and right, just call return (root==null)? 0:dfs(root,1,root.val);
since the last recursion will automatically return the bigger one between the left and right node of the root.

• ``````Make it more simplified.

public int longestConsecutive(TreeNode root) {
if(root==null) return 0;
return Helper(root, 1, root.val);
}

public int Helper(TreeNode root, int count, int val){
if(root==null) return count;
count = (root.val - val == 1)?count+1:1;
int left = Helper(root.left, count, root.val);
int right = Helper(root.right, count, root.val);
return Math.max(Math.max(left, right), count);
}``````

• @nightowl

``````    public int dfs(TreeNode node, int n) {
int left = node.left != null ? dfs(node.left, node.left.val - 1 == node.val ? n + 1 : 1)  : n;
int right = node.right != null ? dfs(node.right, node.right.val - 1 == node.val ? n + 1 : 1) : n;
return Math.max(Math.max(left, right), n);
}
``````

• Just curious, is this solution also takes O(N) ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.