Given a binary tree, the task is to find the length of the longest path which forms an Arithmetic progression. The path can start and end at any node of the tree.
Examples:
Input:
Output: 5
Explanation: The longest path forming an AP is: 3->6->9->12->15Input:
Output: 6
Explanation: The longest path forming an AP is: 2->4->6->8->10->12
Approach: The catch here is that a tree node can only support two AP’s, one with the left child and the other one with the right child. Now, to solve this problem, follow the below steps:
- Create a variable ans to store the length of the longest path.
- Start a depth-first search from the root node, and for each node, find the maximum length path of AP’s till left child and right child.
- Now find the difference between the current node and its left child, say leftDiff and the difference between the current node and its right child, say rightDiff.
- Now find the longest path with difference leftDiff in the left child, say maxLen1 and longest path with difference rightDiff in the right child, say maxLen2.
- If leftDiff = (-1)*rightDiff, then both the branches of the current node form an AP, so change ans to the maximum out of the previous value of ans and maxLen1+maxLen2+1.
- Else, change ans to the maximum out of the previous value of ans, (maxLen1+1) and (maxLen2+1), because only one of the two paths can be selected.
- Now return maxLen1 and maxLen2 along with the difference of the AP from the current node to the parent node.
- Print ans after the function stops.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Tree Nodeclass Node {public: int data; Node *left, *right; Node(int d) { data = d; left = right = NULL; }};// Variable to store the maximum path lengthint ans = 1;// Function to find the maximum length// of a path which forms an APvector<pair<int, int> > maxApPath(Node* root){ vector<pair<int, int> > l = { { INT_MAX, 0 }, { INT_MAX, 0 } }, r = { { INT_MAX, 0 }, { INT_MAX, 0 } }; // Variables to store the difference with // left and right nodes int leftDiff = INT_MAX; int rightDiff = INT_MAX; // If left child exists if (root->left) { l = maxApPath(root->left); leftDiff = (root->data) - (root->left->data); } // If right child exists if (root->right) { r = maxApPath(root->right); rightDiff = (root->data) - (root->right->data); } // Variable to store the maximum length // path in the left subtree in which // the difference between each // node is leftDiff int maxLen1 = 0; // Variable to store the maximum length // path in the right subtree in which // the difference between each // node is rightDiff int maxLen2 = 0; // If a path having the difference // leftDiff is found in left subtree if (leftDiff == l[0].first or l[0].first == INT_MAX) { maxLen1 = l[0].second; } if (leftDiff == l[1].first or l[1].first == INT_MAX) { maxLen1 = max(maxLen1, l[1].second); } // If a path having the difference // rightDiff is found in right subtree if (rightDiff == r[0].first or r[0].first == INT_MAX) { maxLen2 = r[0].second; } if (rightDiff == r[1].first or r[1].first == INT_MAX) { maxLen2 = max(maxLen2, r[1].second); } // If both left and right subtree form AP if (leftDiff == (-1 * rightDiff)) { ans = max(ans, maxLen1 + maxLen2 + 1); } // Else else { ans = max({ ans, maxLen1 + 1, maxLen2 + 1 }); } // Return maximum path for // leftDiff and rightDiff return { { leftDiff, maxLen1 + 1 }, { rightDiff, maxLen2 + 1 } };}// Driver Codeint main(){ // Given Tree Node* root = new Node(1); root->left = new Node(8); root->right = new Node(6); root->left->left = new Node(6); root->left->right = new Node(10); root->right->left = new Node(3); root->right->right = new Node(9); root->left->left->right = new Node(4); root->left->right->right = new Node(12); root->right->right->right = new Node(12); root->left->left->right->right = new Node(2); root->right->right->right->left = new Node(15); root->right->right->right->right = new Node(11); maxApPath(root); cout << ans; return 0;} |
Java
// Java code for the above approachclass GFG{// Tree Nodestatic class Node { int data; Node left, right; Node(int d) { data = d; left = right = null; }};static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Variable to store the maximum path lengthstatic int ans = 1;// Function to find the maximum length// of a path which forms an APstatic pair[] maxApPath(Node root){ pair [] l = { new pair(Integer.MAX_VALUE, 0 ), new pair( Integer.MAX_VALUE, 0 ) }; pair [] r = { new pair( Integer.MAX_VALUE, 0 ), new pair( Integer.MAX_VALUE, 0 ) }; // Variables to store the difference with // left and right nodes int leftDiff = Integer.MAX_VALUE; int rightDiff = Integer.MAX_VALUE; // If left child exists if (root.left!=null) { l = maxApPath(root.left); leftDiff = (root.data) - (root.left.data); } // If right child exists if (root.right!=null) { r = maxApPath(root.right); rightDiff = (root.data) - (root.right.data); } // Variable to store the maximum length // path in the left subtree in which // the difference between each // node is leftDiff int maxLen1 = 0; // Variable to store the maximum length // path in the right subtree in which // the difference between each // node is rightDiff int maxLen2 = 0; // If a path having the difference // leftDiff is found in left subtree if (leftDiff == l[0].first || l[0].first == Integer.MAX_VALUE) { maxLen1 = l[0].second; } if (leftDiff == l[1].first || l[1].first == Integer.MAX_VALUE) { maxLen1 = Math.max(maxLen1, l[1].second); } // If a path having the difference // rightDiff is found in right subtree if (rightDiff == r[0].first || r[0].first == Integer.MAX_VALUE) { maxLen2 = r[0].second; } if (rightDiff == r[1].first || r[1].first == Integer.MAX_VALUE) { maxLen2 = Math.max(maxLen2, r[1].second); } // If both left and right subtree form AP if (leftDiff == (-1 * rightDiff)) { ans = Math.max(ans, maxLen1 + maxLen2 + 1); } // Else else { ans = Math.max( Math.max(ans, maxLen1 + 1), maxLen2 + 1 ); } // Return maximum path for // leftDiff and rightDiff return new pair[] { new pair(leftDiff, maxLen1 + 1 ), new pair( rightDiff, maxLen2 + 1 ) };}// Driver Codepublic static void main(String[] args){ // Given Tree Node root = new Node(1); root.left = new Node(8); root.right = new Node(6); root.left.left = new Node(6); root.left.right = new Node(10); root.right.left = new Node(3); root.right.right = new Node(9); root.left.left.right = new Node(4); root.left.right.right = new Node(12); root.right.right.right = new Node(12); root.left.left.right.right = new Node(2); root.right.right.right.left = new Node(15); root.right.right.right.right = new Node(11); maxApPath(root); System.out.print(ans);}}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach # Tree Nodeclass Node: def __init__(self, d): self.data = d self.left = self.right = None# Variable to store the maximum path lengthans = 1;# Function to find the maximum length# of a path which forms an APdef maxApPath(root): l = [{ "first": 10 ** 9, "second": 0 }, { "first": 10 ** 9, "second": 0 }] r = [{ "first": 10 ** 9, "second": 0 }, { "first": 10 ** 9, "second": 0 }]; # Variables to store the difference with # left and right nodes leftDiff = 10 ** 9; rightDiff = 10 ** 9; # If left child exists if (root.left): l = maxApPath(root.left); leftDiff = (root.data) - (root.left.data); # If right child exists if (root.right) : r = maxApPath(root.right); rightDiff = (root.data) - (root.right.data); # Variable to store the maximum length # path in the left subtree in which # the difference between each # node is leftDiff maxLen1 = 0; # Variable to store the maximum length # path in the right subtree in which # the difference between each # node is rightDiff maxLen2 = 0; # If a path having the difference # leftDiff is found in left subtree if (leftDiff == l[0]["first"] or l[0]["first"] == 10 ** 9): maxLen1 = l[0]["second"]; if (leftDiff == l[1]["first"] or l[1]["first"] == 10 ** 9): maxLen1 = max(maxLen1, l[1]["second"]); # If a path having the difference # rightDiff is found in right subtree if (rightDiff == r[0]["first"] or r[0]["first"] == 10 ** 9): maxLen2 = r[0]["second"]; if (rightDiff == r[1]["first"] or r[1]["first"] == 10 ** 9): maxLen2 = max(maxLen2, r[1]["second"]); global ans; # If both left and right subtree form AP if (leftDiff == (-1 * rightDiff)): ans = max(ans, maxLen1 + maxLen2 + 1); # Else else: ans = max(ans, max(maxLen1 + 1, maxLen2 + 1)); # Return maximum path for # leftDiff and rightDiff return [{ "first": leftDiff, "second": maxLen1 + 1 }, { "first": rightDiff, "second": maxLen2 + 1 }];# Driver Code# Given Treeroot = Node(1);root.left = Node(8);root.right = Node(6);root.left.left = Node(6);root.left.right = Node(10);root.right.left = Node(3);root.right.right = Node(9);root.left.left.right = Node(4);root.left.right.right = Node(12);root.right.right.right = Node(12);root.left.left.right.right = Node(2);root.right.right.right.left = Node(15);root.right.right.right.right = Node(11);maxApPath(root);print(ans);# This code is contributed by gfgking |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG { // Tree Node public class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; } }; public class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Variable to store the maximum path length static int ans = 1; // Function to find the maximum length // of a path which forms an AP static pair[] maxApPath(Node root) { pair[] l = { new pair(int.MaxValue, 0), new pair(int.MaxValue, 0) }; pair[] r = { new pair(int.MaxValue, 0), new pair(int.MaxValue, 0) }; // Variables to store the difference with // left and right nodes int leftDiff = int.MaxValue; int rightDiff = int.MaxValue; // If left child exists if (root.left != null) { l = maxApPath(root.left); leftDiff = (root.data) - (root.left.data); } // If right child exists if (root.right != null) { r = maxApPath(root.right); rightDiff = (root.data) - (root.right.data); } // Variable to store the maximum length // path in the left subtree in which // the difference between each // node is leftDiff int maxLen1 = 0; // Variable to store the maximum length // path in the right subtree in which // the difference between each // node is rightDiff int maxLen2 = 0; // If a path having the difference // leftDiff is found in left subtree if (leftDiff == l[0].first || l[0].first == int.MaxValue) { maxLen1 = l[0].second; } if (leftDiff == l[1].first || l[1].first == int.MaxValue) { maxLen1 = Math.Max(maxLen1, l[1].second); } // If a path having the difference // rightDiff is found in right subtree if (rightDiff == r[0].first || r[0].first == int.MaxValue) { maxLen2 = r[0].second; } if (rightDiff == r[1].first || r[1].first == int.MaxValue) { maxLen2 = Math.Max(maxLen2, r[1].second); } // If both left and right subtree form AP if (leftDiff == (-1 * rightDiff)) { ans = Math.Max(ans, maxLen1 + maxLen2 + 1); } // Else else { ans = Math.Max(Math.Max(ans, maxLen1 + 1), maxLen2 + 1); } // Return maximum path for // leftDiff and rightDiff return new pair[] { new pair(leftDiff, maxLen1 + 1), new pair(rightDiff, maxLen2 + 1) }; } // Driver Code public static void Main(String[] args) { // Given Tree Node root = new Node(1); root.left = new Node(8); root.right = new Node(6); root.left.left = new Node(6); root.left.right = new Node(10); root.right.left = new Node(3); root.right.right = new Node(9); root.left.left.right = new Node(4); root.left.right.right = new Node(12); root.right.right.right = new Node(12); root.left.left.right.right = new Node(2); root.right.right.right.left = new Node(15); root.right.right.right.right = new Node(11); maxApPath(root); Console.Write(ans); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach // Tree Node class Node { constructor(d) { this.data = d; this.left = this.right = null; } }; // Variable to store the maximum path length let ans = 1; // Function to find the maximum length // of a path which forms an AP function maxApPath(root) { let l = [{ first: Number.MAX_VALUE, second: 0 }, { first: Number.MAX_VALUE, second: 0 }], r = [{ first: Number.MAX_VALUE, second: 0 }, { first: Number.MAX_VALUE, second: 0 }]; // Variables to store the difference with // left and right nodes let leftDiff = Number.MAX_VALUE; let rightDiff = Number.MAX_VALUE; // If left child exists if (root.left) { l = maxApPath(root.left); leftDiff = (root.data) - (root.left.data); } // If right child exists if (root.right) { r = maxApPath(root.right); rightDiff = (root.data) - (root.right.data); } // Variable to store the maximum length // path in the left subtree in which // the difference between each // node is leftDiff let maxLen1 = 0; // Variable to store the maximum length // path in the right subtree in which // the difference between each // node is rightDiff let maxLen2 = 0; // If a path having the difference // leftDiff is found in left subtree if (leftDiff == l[0].first || l[0].first == Number.MAX_VALUE) { maxLen1 = l[0].second; } if (leftDiff == l[1].first || l[1].first == Number.MAX_VALUE) { maxLen1 = Math.max(maxLen1, l[1].second); } // If a path having the difference // rightDiff is found in right subtree if (rightDiff == r[0].first || r[0].first == Number.MAX_VALUE) { maxLen2 = r[0].second; } if (rightDiff == r[1].first || r[1].first == Number.MAX_VALUE) { maxLen2 = Math.max(maxLen2, r[1].second); } // If both left and right subtree form AP if (leftDiff == (-1 * rightDiff)) { ans = Math.max(ans, maxLen1 + maxLen2 + 1); } // Else else { ans = Math.max(ans, Math.max(maxLen1 + 1, maxLen2 + 1)); } // Return maximum path for // leftDiff and rightDiff return [{ first: leftDiff, second: maxLen1 + 1 }, { first: rightDiff, second: maxLen2 + 1 }]; } // Driver Code // Given Tree let root = new Node(1); root.left = new Node(8); root.right = new Node(6); root.left.left = new Node(6); root.left.right = new Node(10); root.right.left = new Node(3); root.right.right = new Node(9); root.left.left.right = new Node(4); root.left.right.right = new Node(12); root.right.right.right = new Node(12); root.left.left.right.right = new Node(2); root.right.right.right.left = new Node(15); root.right.right.right.right = new Node(11); maxApPath(root); document.write(ans); // This code is contributed by Potta Lokesh </script> |
Output:
6
Time Complexity: O(N) where N is number of nodes in the Tree
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
