Time:O(n) Space:O(h) C++ struct T { int inc; // length of longest incrementing branch int dec; // length of longest decrementing branch }; class Solution { public: int longestConsecutive(TreeNode* root) { int ans = 0; longestPath(root, ans); return ans; } private: // return (longest increment, longest decrement) T longestPath(TreeNode* root, int& ans) { if (!root) return {0, 0}; int inc = 1; int dec = 1; if (root->left) { T l = longestPath(root->left, ans); if (root->val + 1 == root->left->val) inc = l.inc + 1; else if (root->val - 1 == root->left->val) dec = l.dec + 1; } if (root->right) { T r = longestPath(root->right, ans); if (root->val + 1 == root->right->val) inc = max(inc, r.inc + 1); else if (root->val - 1 == root->right->val) dec = max(dec, r.dec + 1); } ans = max(ans, inc + dec - 1); return {inc, dec}; } }; JAVA class T { public int inc; // length of longest incrementing branch public int dec; // length of longest decrementing branch public T(int inc, int dec) { this.inc = inc; this.dec = dec; } } class Solution { public int longestConsecutive(TreeNode root) { longestPath(root); return ans; } private int ans = 0; // return (longest increment, longest decrement) private T longestPath(TreeNode root) { if (root == null) return new T(0, 0); int inc = 1; int dec = 1; if (root.left != null) { T l = longestPath(root.left); if (root.val + 1 == root.left.val) inc = l.inc + 1; else if (root.val - 1 == root.left.val) dec = l.dec + 1; } if (root.right != null) { T r = longestPath(root.right); if (root.val + 1 == root.right.val) inc = Math.max(inc, r.inc + 1); else if (root.val - 1 == root.right.val) dec = Math.max(dec, r.dec + 1); } ans = Math.max(ans, inc + dec - 1); return new T(inc, dec); } }