298. Binary Tree Longest Consecutive Sequence

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem specifies a binary tree and requires us to find the length of the longest consecutive sequence path within it. A consecutive sequence path is defined as a path in which adjacent nodes in the path have values that differ by exactly one. An important aspect of this problem is that the path does not need to begin at the root of the tree; it can start at any node. Additionally, the path is uni-directional, meaning once you move from a parent node to a child node, you cannot move back up to the parent.

Intuition

To solve this problem, we can use a Depth-First Search (DFS) approach. The idea is to explore each node starting from the root and recursively check its children to find the longest increasing consecutive sequence that includes the node itself as either the start or some part of the sequence. The DFS approach allows us to go as deep as possible down each path before backtracking, which is necessary to examine all potential paths.

Specifically, at each node, we will perform the following actions:

  1. We check if the node is None. If it is, there's no sequence to be found, so we return 0.
  2. We recursively call the dfs function on the left and right children. The returned values represent the lengths of the consecutive sequences that start with the children.
  3. We increment the lengths by one to include the current node. At this point, the length assumes that the current node is part of the sequence.
  4. We need to check if the child node actually follows the consecutive sequence. We do this by ensuring that the difference between the value of the child node and the current node is exactly one. If not, we reset the length to 1 as the sequence can only start from the current node.
  5. We calculate the temporary longest sequence t that can be created by the current node with its children by taking the maximum of the lengths from its left and right child sequences.
  6. We maintain a global variable ans that keeps track of the longest sequence found so far. After processing each node, we update ans with the maximum value between ans and t.

In the end, we return ans, which will contain the maximum length of the longest consecutive sequence path found anywhere in the binary tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

To implement the solution approach for finding the longest consecutive sequence path in a binary tree, the Depth-First Search (DFS) algorithm is used, utilizing recursion. The code defines a helper function dfs within the Solution class's longestConsecutive method to perform the DFS.

Here's how the implementation works step by step:

  1. The dfs function is defined to take a TreeNode as an input and returns an integer which is the length of the longest consecutive path that can be formed including the given node. If the node is None, the function returns 0, indicating that a null node cannot contribute to the length of a sequence.

  2. Invoking dfs recursively, we analyze the left and right subtrees by calling dfs(root.left) and dfs(root.right). The returned values from both calls represent the lengths of consecutive sequence paths starting at the left and right children, respectively.

  3. A value of 1 is added to both lengths to include the current root in the sequence. This is based on the assumption that the current root extends the paths from its children by one.

  4. Two if conditions ensure that the sequence is indeed consecutive. If the left child's value is not one more than the current node's value or if the right child's value is not one more than the current node's value, the corresponding sequence length is reset to 1, indicating that a new sequence can start at root.

  5. The temporary maximum length t is determined by taking the maximum of the adjusted values from the left and right sequences.

  6. The non-local variable ans is used to keep track of the global maximum. This variable is updated (if necessary) every time a new local maximum is found, ensuring it always holds the length of the longest consecutive sequence seen so far.

  7. After updating ans, t is returned, referring to the longest sequence that includes the current root.

The recursive DFS strategy allows each node to contribute to the sequential path in a bottom-up approach, combining individual paths from leaf nodes to the root (or any other starting node), updating the global maximum along the way.

In the main function longestConsecutive, ans is initialized to 0, then the recursive dfs process is kickstarted by passing the root node. After exploring all possible nodes, the final ans represents the solution and is returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's assume we have the following binary tree structure to help illustrate the solution approach:

1    1
2   / \
3  2   3
4 /     \
54       2
6       /
7      3

We need to find the length of the longest consecutive sequence path in this tree.

Here's a step-by-step walkthrough with our sample tree:

  1. Start with the root node (1). The dfs function is called with node 1 as input.

  2. Call dfs recursively for the left child (dfs(2)) and right child (dfs(3)).

  3. In dfs(2), it recursive calls dfs(4).

    • dfs(4) returns 1 because it is a leaf node and has no children.
    • Since 4 is one more than 2, we increase the sequence length to 2 (initial 1, plus 1 since it's consecutive).
    • This sequence length is returned to the dfs call on node 2.

  4. For the right child dfs(3) of root node 1:

    • dfs(3) calls dfs(2), which then calls dfs(3) on its own left child.
    • The left child 3 is a leaf and returns 1.
    • The node 2 has a child with a value of one less than itself, so this is not an incrementing consecutive sequence.
    • dfs(2) resets the sequence length to 1.

  5. Now we compare the temporary lengths from left and right children of the root. For the left side, we got a length of 2 (from 1->2->4 sequence), and from the right side, we have a length of 1 (since the 1->3->2 sequence isn't increasing consecutively).

  6. The temporary maximum t at root node 1 is 2 (the maximum of 2 and 1). However, root 1 does not increment either sequence, so we do not add 1 to it.

  7. We update the global maximum ans if t is greater than the current ans. For the root node, ans is updated to 2.

  8. dfs(1) returns t, which is 2.

Hence after running our dfs algorithm on the binary tree, we find that the longest consecutive sequence path has a length of 2 from the sequence 1->2->4.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
10        # Helper function that uses depth-first search to find the longest consecutive sequence.
11        def dfs(node: Optional[TreeNode]) -> int:
12            if node is None:
13                return 0
14            left_length = dfs(node.left) + 1  # Length of the sequence from the left child
15            right_length = dfs(node.right) + 1  # Length of the sequence from the right child
16          
17            # If the left child is not consecutive, reset the length for that path
18            if node.left and node.left.val - node.val != 1:
19                left_length = 1
20          
21            # If the right child is not consecutive, reset the length for that path
22            if node.right and node.right.val - node.val != 1:
23                right_length = 1
24          
25            # The longest path through the current node is the larger of its two children's paths
26            current_max_length = max(left_length, right_length)
27          
28            # Update the global answer if the current path is longer than the previously found paths
29            nonlocal max_length
30            max_length = max(max_length, current_max_length)
31          
32            # Return the length of the longest path passing through this node
33            return current_max_length
34
35        max_length = 0  # Initialize the maximum length variable
36        dfs(root)  # Start DFS from the root of the tree
37        return max_length  # Return the longest consecutive sequence length found
38
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17class Solution {
18    private int longestStreak;
19
20    /**
21     * Finds the length of the longest consecutive sequence path in a binary tree.
22     * @param root The root of the binary tree.
23     * @return The length of the longest consecutive sequence.
24     */
25    public int longestConsecutive(TreeNode root) {
26        dfs(root);
27        return longestStreak;
28    }
29
30    /**
31     * Depth-first search helper method that traverses the tree and finds the longest consecutive path.
32     * The current node's value must be exactly one more than its parent's value to be part of the sequence.
33     * @param node The current node in the DFS traversal.
34     * @return The length of the longest path ending at the current node.
35     */
36    private int dfs(TreeNode node) {
37        if (node == null) {
38            return 0;
39        }
40      
41        int leftLength = dfs(node.left) + 1; // Length of left child sequence + current node
42        int rightLength = dfs(node.right) + 1; // Length of right child sequence + current node
43      
44        // If the left child's value is not consecutive, reset left sequence length
45        if (node.left != null && node.left.val - node.val != 1) {
46            leftLength = 1;
47        }
48      
49        // If the right child's value is not consecutive, reset right sequence length
50        if (node.right != null && node.right.val - node.val != 1) {
51            rightLength = 1;
52        }
53      
54        // The maximum length of the consecutive sequence at the current node
55        int currentMax = Math.max(leftLength, rightLength);
56      
57        // Update the longest streak if the current max is greater
58        longestStreak = Math.max(longestStreak, currentMax);
59      
60        return currentMax;
61    }
62}
63
1#include <functional> // We should include the necessary header for std::function
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Function to find the length of the longest consecutive sequence in a binary tree.
16    int longestConsecutive(TreeNode* root) {
17        int maxLength = 0; // Initialize the maxLength to keep track of the longest sequence.
18      
19        // Recursive lambda function to perform a depth-first search on the tree.
20        // It returns the length of the longest consecutive sequence starting at 'node'.
21        std::function<int(TreeNode*)> dfs = [&](TreeNode* node) {
22            if (!node) {
23                // If the node is null, return 0 since there is no sequence.
24                return 0;
25            }
26            // Recursively find the length of the longest consecutives sequences in the left and right subtrees.
27            // We start by assuming both sequences include the current node, hence +1.
28            int leftLength = dfs(node->left) + 1;
29            int rightLength = dfs(node->right) + 1;
30
31            // If the left child exists and doesn't follow the consecutive property, reset the leftLength.
32            if (node->left && node->left->val - node->val != 1) {
33                leftLength = 1;
34            }
35          
36            // If the right child exists and doesn't follow the consecutive property, reset the rightLength.
37            if (node->right && node->right->val - node->val != 1) {
38                rightLength = 1;
39            }
40          
41            // The longest sequence at the current node is the max of the left and right sequences.
42            int currentLength = std::max(leftLength, rightLength);
43          
44            // Update the maxLength if the sequence at the current node is the longest one found so far.
45            maxLength = std::max(maxLength, currentLength);
46          
47            // Return the length of the longest sequence at the current node.
48            return currentLength;
49        };
50      
51        // Perform the depth-first search starting from the root.
52        dfs(root);
53      
54        // After the DFS, maxLength contains the length of the longest consecutive sequence in the tree.
55        return maxLength;
56    }
57};
58
1// Type definition for a binary tree node.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8// Function that returns the length of the longest consecutive sequence in the binary tree.
9function longestConsecutive(root: TreeNode | null): number {
10    let longestSequence = 0; // This variable will hold the longest sequence found.
11
12    // Helper function that performs depth-first search to find the longest consecutive sequence.
13    const findLongestConsecutive = (currentNode: TreeNode | null): number => {
14        if (currentNode === null) {
15            return 0;
16        }
17
18        // Recursively find the lengths for left and right subtrees.
19        let leftLength = findLongestConsecutive(currentNode.left) + 1;
20        let rightLength = findLongestConsecutive(currentNode.right) + 1;
21
22        // If the left child is not consecutively increasing, reset the left sequence length.
23        if (currentNode.left && currentNode.left.val - currentNode.val !== 1) {
24            leftLength = 1;
25        }
26
27        // If the right child is not consecutively increasing, reset the right sequence length.
28        if (currentNode.right && currentNode.right.val - currentNode.val !== 1) {
29            rightLength = 1;
30        }
31
32        // Take the longer sequence of the two.
33        const currentMax = Math.max(leftLength, rightLength);
34
35        // Update the longest sequence found so far.
36        longestSequence = Math.max(longestSequence, currentMax);
37
38        // Return the longer sequence found at the current node.
39        return currentMax;
40    };
41
42    // Start the search from the root of the binary tree.
43    findLongestConsecutive(root);
44
45    // Return the longest consecutive sequence length found.
46    return longestSequence;
47}
48
Not Sure What to Study? Take the 2-min Quiz๏ผš

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

The given code performs a depth-first search (DFS) on a binary tree to find the length of the longest consecutive sequence.

Time Complexity:

The time complexity of the DFS function is O(N), where N is the total number of nodes in the binary tree. This is because the algorithm visits each node exactly once to calculate the longest consecutive path that includes that node as the sequence start.

Space Complexity:

The space complexity of the DFS function is O(H), where H is the height of the binary tree. The reason for this is the recursive stack space which, in the worst-case scenario (a completely unbalanced tree), could be equal to the number of nodes N (thus O(N)), but for a balanced tree, it will be O(log N). H captures this as it ranges from log N to N depending on the balance of the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ