LeetCode 298: Binary Tree Longest Consecutive Sequence Solution

Master LeetCode problem 298 (Binary Tree Longest Consecutive Sequence), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

298. Binary Tree Longest Consecutive Sequence

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

We need to find the length of the longest consecutive sequence path in a binary tree.
A consecutive sequence is a sequence of nodes from parent to child where the values of the nodes are consecutive integers.
We can perform a depth-first search (DFS) traversal of the tree to track the consecutive sequence length.
We pass the current node, the expected value of the next node in the sequence, and the current length of the consecutive sequence.
If the current node's value is equal to the expected value, we increase the current length by 1.
We recursively check the left and right children with the updated expected value and length, and return the maximum length from both branches.
At each node, we compare the current length with the global maximum length. :

Solution Code

class Solution {
    int maxLen = 0;
    
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        dfs(root, root.val, 0);
        return maxLen;
    }
    
    private void dfs(TreeNode node, int expected, int length) {
        if (node == null) return;
        
        if (node.val == expected) {
            length++;
        } else {
            length = 1;
        }
        
        maxLen = Math.max(maxLen, length);
        
        dfs(node.left, node.val + 1, length);
        dfs(node.right, node.val + 1, length);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 298 (Binary Tree Longest Consecutive Sequence)?

This page provides optimized solutions for LeetCode problem 298 (Binary Tree Longest Consecutive Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 298 (Binary Tree Longest Consecutive Sequence)?

The time complexity for LeetCode 298 (Binary Tree Longest Consecutive Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 298 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 298 in Java, C++, or Python.

Back to LeetCode Solutions