w3resource

Java: Find the length of the longest consecutive sequence path of a given binary tree

Java Basic: Exercise-184 with Solution

Longest Consecutive Path in Tree

Write a Java program to find the length of the longest consecutive sequence path in a given binary tree.

Note: The longest consecutive path need to be from parent to child.

Sample Binary tree:

Java Basic Exercises: Find the length of the longest consecutive sequence path of a given binary tree.

Result:

Java Basic Exercises: Find the length of the longest consecutive sequence path of a given binary tree.

Sample Solution:

Java Code:

// Importing necessary Java utilities
import java.util.*;

// TreeNode class definition
class TreeNode {
    public int val;
    public TreeNode left, right;

    // TreeNode class constructor
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

// Main class Solution
public class Solution {
    // Main method
    public static void main(String[] args) {
        // Creating the tree nodes and constructing the binary tree
        TreeNode a = new TreeNode(1);
        a.right = new TreeNode(3);
        a.right.left = new TreeNode(2);
        a.right.right = new TreeNode(4);
        a.right.right.right = new TreeNode(5);
        a.right.right.right.right = new TreeNode(6);

        // Printing the length of the longest consecutive sequence path
        System.out.println("Length of the longest consecutive sequence path: " + longest_Consecutive(a));
    }

    // Method to find the longest consecutive sequence path in a binary tree
    public static int longest_Consecutive(TreeNode root) {
        // Base case: if the root is null, return 0
        if (root == null) {
            return 0;
        }

        // Compute the result by recursively traversing the tree
        int result = diffn(root, 1) + diffn(root, -1);
        return Math.max(result, Math.max(longest_Consecutive(root.left), longest_Consecutive(root.right)));
    }

    // Helper method to compute the depth of the consecutive sequence path
    private static int diffn(TreeNode tnode, int diff) {
        // Base case: if the tree node is null, return 0
        if (tnode == null) {
            return 0;
        }

        // Initialize depths for left and right subtrees
        int left_depth = 0, right_depth = 0;

        // Check if there exists a consecutive sequence path in left and right subtrees
        if (tnode.left != null && tnode.val - tnode.left.val == diff) {
            left_depth = diffn(tnode.left, diff) + 1;
        }
        if (tnode.right != null && tnode.val - tnode.right.val == diff) {
            right_depth = diffn(tnode.right, diff) + 1;
        }

        // Return the maximum depth among left and right consecutive sequence paths
        return Math.max(left_depth, right_depth);
    }
} 

Sample Output:

Length of the longest consecutive sequence path:  4

Flowchart:

Flowchart: Java exercises: Find the length of the longest consecutive sequence path of a given binary tree.

Java Code Editor:

Company:  Google NetEase

Contribute your code and comments through Disqus.

Previous: Write a Java program to accept a positive number and repeatedly add all its digits until the result has only one digit.
Next: Write a Java program to check if two given strings are isomorphic or not.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/java-exercises/basic/java-basic-exercise-184.php