Binary Tree Longest Consecutive Sequence

Question:

Similar to https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
but the difference is : path can start from and end at any internal node or leaf node.

Answer:

public class BinaryTreeLongestConsecutiveSeq2 {

static int maxLen = 0;

static class Node {

int val;

Node left;

Node right;

public Node(int val) {

this.val = val;

left = null;

right = null;

}

}

public static int[] longestPathUtil(Node root) {

int[] res = { 0, 0 };

if (root == null)

return res;

//System.out.println("root = " + root.val);

//edge case for leaf node!

int smallerPathLen = 1;

int biggerPathLen = 1;

int[] leftPathRes = longestPathUtil(root.left);

int[] rightPathRes = longestPathUtil(root.right);

        //System.out.println("left res: " + res[0] + "," + res[1]);

if (root.left != null) {

if (root.left.val < root.val) {

smallerPathLen = Math.max(smallerPathLen, leftPathRes[0] + 1);

} else if (root.left.val > root.val) {

biggerPathLen = Math.max(biggerPathLen, leftPathRes[1] + 1);

}

}

if (root.right != null) {

if (root.right.val < root.val) {

smallerPathLen = Math.max(smallerPathLen, rightPathRes[0] + 1);

} else if (root.right.val > root.val) {

biggerPathLen = Math.max(biggerPathLen, rightPathRes[1] + 1);

}

}

// update longest increasing path len!

int totalLen = smallerPathLen + biggerPathLen - 1;

maxLen = Math.max(maxLen, totalLen);

res[0] = smallerPathLen;

res[1] = biggerPathLen;

//System.out.println("left = " + res[0] + ", right = " + res[1]);

return res;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Node root = new Node(8);

root.left = new Node(4);

root.right = new Node(10);

root.left.left = new Node(3);

root.left.right = new Node(7);

root.right.left = new Node(9);

root.right.right = new Node(11);

root.left.right.left = new Node(6);

longestPathUtil(root);

System.out.println(maxLen);

}

}