Binary Tree Longest Consecutive Sequence Lintcode

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is3-4-5, so return3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is2-3,not3-2-1, so return2.

Analysis

There are preorder and postorder solutions, where postorder seems to be easier to understand. The difficulty of this problem lies in the boundary cases.

Solution - Preoder

int maxLength = -1;
public int longestConsecutive(TreeNode root) {
    int pathLength = 0;
    if (root == null){
        return pathLength;
    }

    helper(root, pathLength, root.val);
    return maxLength;
}

public void helper(TreeNode root, int pathLength, int next){
    if (root == null){
       maxLength = Math.max(maxLength, pathLength);
       return;
    }

    if (root.val == next){
        pathLength += 1;
    } else {
        maxLength = Math.max(maxLength, pathLength);
        pathLength = 1;
    }

    if (root.left == null && root.right == null){
        maxLength = Math.max(maxLength, pathLength);
        return;
    }

    if (root.left != null){    
         helper(root.left, pathLength,  root.val + 1);
    }  


    if (root.right != null){            
    helper(root.right, pathLength,  root.val + 1);
    }
}

Solution 2 - postorder

int maxSeqLength = Integer.MIN_VALUE;

public int longestConsecutive(TreeNode root) {
    helper(root);
    return maxSeqLength;
}

public int helper(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left);
    int right = helper(root.right);

    int l_left = 1;
    if (left > 0) {
        if (root.val + 1 == root.left.val) {
            l_left = left + 1;
        }
    }

    int l_right = 1;
    if (right > 0) {
        if (root.val + 1 == root.right.val) {
            l_right = right + 1;
        }
    }

    int l_max = Math.max(l_left, l_right);
    maxSeqLength = Math.max(l_max, maxSeqLength);
    return l_max;
}

Binary Tree Longest Consecutive Sequence II - Lintcode

Given a binary tree, find the length of the longest consecutive sequence path. The path could be start and end at any node in the tree.

Example

    1
   / \
  2   0
 /
3

Return4//0-1-2-3-4

Analysis

Postorder traversal seems to be easier to understand and implement. (TRY to implement it with preorder traversal!) Starting at the leave (left then right), the len, up and down are calculated for each treenode. with up and down being the consecutive sequence count and len being the sum of the counts. The discontinuation of the sequence will reset the up and down but not the len. Therefore the len at the root node is the count for the longest consecutive sequence. Postorder means that the len, up and down information needs to be returned as the return parameter; where in preorder, these parameter can be passed as method parameters.

length = Math.max(Math.max(left.maxLength, right.maxLength), up + down + 1);
* the + 1 is for the current node

class ResultType{
    int maxLength;
    int maxUp;
    int maxDown;
    public ResultType(int len, int up, int down){
        this.maxLength = len;
        this.maxUp = up;
        this.maxDown = down;
    }
} 
public int longestConsecutive2(TreeNode root) {
    ResultType result = helper(root);
    return result.maxLength;
}

public ResultType helper(TreeNode node){
    if (node == null){
        return new ResultType(0, 0, 0);
    }


    ResultType left = helper(node.left);
    ResultType right = helper(node.right);

    int length = 0;
    int up = 0;
    int down = 0;

    if (node.left != null){
        if (node.left.val + 1 == node.val){
            up = Math.max(up, left.maxUp + 1);
        }

        if (node.left.val - 1 == node.val){
            down = Math.max(down, left.maxDown + 1);
        }
    }

    if (node.right != null){
        if (node.right.val + 1 == node.val){
            up = Math.max(up, right.maxUp + 1);
        }

        if (node.right.val - 1 == node.val){
            down = Math.max(down, right.maxDown + 1);
        }
    }

    length = Math.max(Math.max(left.maxLength, right.maxLength), up + down + 1);

    return new ResultType(length, up, down);
}