298. Binary Tree Longest Consecutive Sequence

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/*
Top Down DFS Approach

Time Complexity: O(N)
Space Complexity: O(H)

N = Number of nodes in the binary tree.
H = Height of the binary Tree. This will be equal to N if the tree is skewed.
*/
class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfsHelper(root, root.val, 0);
    }

    public int dfsHelper(TreeNode node, int target, int curLength) {
        if (node == null) {
            return curLength;
        }
        curLength = node.val == target ? curLength+1 : 1;
        return Math.max(curLength, Math.max(dfsHelper(node.left, node.val+1, curLength), dfsHelper(node.right, node.val+1, curLength)));
    }
}

/*
Iterative Approach

Time Complexity: O(N)
Space Complexity: O(H)

N = Number of Nodes in the binary tree.
H = Height of the binary Tree. This will be equa to N if the tree is skewed.
*/
import javafx.util.Pair;
class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxLength = 0;
        Stack<Pair<TreeNode, Integer>> stack = new Stack();
        stack.push(new Pair<TreeNode, Integer>(root, 1));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> pair = stack.pop();
            TreeNode curNode = pair.getKey();
            int curLength = pair.getValue();
            maxLength = Math.max(maxLength, curLength);
            if (curNode.right != null) {
                if (curNode.right.val == curNode.val+1) {
                    stack.push(new Pair<TreeNode, Integer>(curNode.right, curLength+1));
                } else {
                    stack.push(new Pair<TreeNode, Integer>(curNode.right, 1));
                }
            }
            if (curNode.left != null) {
                if (curNode.left.val == curNode.val+1) {
                    stack.push(new Pair<TreeNode, Integer>(curNode.left, curLength+1));
                } else {
                    stack.push(new Pair<TreeNode, Integer>(curNode.left, 1));
                }
            }
        }
        return maxLength;
    }
}