Java  

Longest Consecutive Path in Binary Tree (Java)

Problem Statement

Given the root of a binary tree, find the length of the longest path where every child node's value is exactly 1 greater than its parent.

The path:

  • Must move only from parent to child.

  • Must contain consecutive increasing values.

If no consecutive path of length greater than 1 exists, return -1.

Example 1

        1
       / \
      2   3

Consecutive path:

1 → 2

Length = 2

Output

2

Example 2

        10
       /  \
     20    30
     /     / \
   40     60 90

There is no child whose value is exactly parent + 1.

Output

-1

Approach

We use Depth First Search (DFS) to visit every node in the tree.

At each node, we keep track of:

  • Parent's value

  • Current consecutive sequence length

For every node:

  • If the current node's value is parent + 1

    • Extend the current sequence.

  • Otherwise

    • Start a new sequence from this node.

During traversal, we continuously update the maximum sequence length.

Finally:

  • If the maximum length is only 1, return -1.

  • Otherwise, return the maximum length.

Algorithm

  1. If the tree is empty, return -1.

  2. Start DFS from the root.

  3. Compare the current node with its parent.

  4. Increase the sequence length if consecutive.

  5. Otherwise, reset the sequence length to 1.

  6. Update the global maximum.

  7. Recursively process the left child.

  8. Recursively process the right child.

  9. Return the answer.

Java Code

class Solution {
    int max = 1;

    public int longestConsecutive(Node root) {
        if (root == null)
            return -1;

        dfs(root, root.data - 1, 0);

        return max == 1 ? -1 : max;
    }

    private void dfs(Node node, int parent, int len) {
        if (node == null)
            return;

        if (node.data == parent + 1)
            len++;
        else
            len = 1;

        max = Math.max(max, len);

        dfs(node.left, node.data, len);
        dfs(node.right, node.data, len);
    }
}

Code Explanation

Global Variable

int max = 1;

Stores the maximum consecutive sequence length found during traversal.

Initially, every node itself forms a sequence of length 1.

longestConsecutive()

public int longestConsecutive(Node root)

This is the main function.

Check for Empty Tree

if (root == null)
    return -1;

If there are no nodes, no consecutive path exists.

Start DFS

dfs(root, root.data - 1, 0);

We call DFS with:

  • Current node = root

  • Parent value = root.data - 1

  • Current length = 0

Why root.data - 1?

Suppose the root value is:

10

We pass:

parent = 9

Inside DFS:

10 == 9 + 1

So the root becomes the beginning of a valid sequence.

Return Answer

return max == 1 ? -1 : max;

If the maximum sequence length is only 1, that means no parent-child consecutive path exists.

So return:

-1

Otherwise, return the maximum length.

DFS Function

private void dfs(Node node, int parent, int len)

Parameters

  • node → Current node

  • parent → Parent's value

  • len → Current consecutive length

Base Case

if (node == null)
    return;

Stop recursion when the node becomes null.

Check Consecutive Condition

if (node.data == parent + 1)
    len++;
else
    len = 1;

There are two cases.

Case 1

The current node continues the sequence.

Example:

5
 \
  6

Since:

6 == 5 + 1

Increase the length.

Case 2

The sequence breaks.

Example:

5
 \
  8

Since:

8 != 5 + 1

Start a new sequence.

len = 1;

Update Maximum

max = Math.max(max, len);

Store the largest sequence found so far.

Example:

Current maximum:

3

Current length:

4

After update:

max = 4

Visit Left Child

dfs(node.left, node.data, len);

The current node becomes the parent for the left child.

Visit Right Child

dfs(node.right, node.data, len);

The current node becomes the parent for the right child.

Both recursive calls carry the updated sequence length.

Dry Run

Consider:

        1
       / \
      2   4
     /
    3

Initially:

max = 1

Visit Node 1:

parent = 0

1 == 0 + 1

len = 1

max = 1

Visit Node 2:

parent = 1

2 == 1 + 1

len = 2

max = 2

Visit Node 3:

parent = 2

3 == 2 + 1

len = 3

max = 3

Visit Node 4:

parent = 1

4 != 2

len = 1

max = 3

Traversal ends.

Answer:

3

Recursion Tree

dfs(1)

│
├── dfs(2)
│      │
│      └── dfs(3)
│
└── dfs(4)

Each recursive call carries:

  • Parent value

  • Current sequence length

Complexity Analysis

Time Complexity

O(n)

Every node is visited exactly once.

Auxiliary Space

O(h)

Where h is the height of the tree.

  • Best case (balanced tree): O(log n)

  • Worst case (skewed tree): O(n)

Key Points

  • DFS is used to traverse the tree.

  • Pass the parent value and current sequence length in recursion.

  • Increase the length only when child = parent + 1.

  • Otherwise, reset the sequence length to 1.

  • Keep updating the global maximum.

  • Return -1 if no consecutive parent-child path longer than one node exists.

Summary

This solution uses a Depth First Search (DFS) traversal to efficiently find the longest parent-to-child consecutive increasing path in a binary tree. By tracking the parent's value and the current sequence length during recursion, the algorithm updates the maximum sequence length in a single traversal. If no consecutive path longer than one node is found, it returns -1 as required.

Membership not found