Longest Arithmetic Progression path in given Binary Tree

0 0 10 minutes read

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->15

Input:

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 Node
class Node {
public:
    int data;
    Node *left, *right;
    Node(int d)
    {
        data = d;
        left = right = NULL;
    }
};
 
// Variable to store the maximum path length
int ans = 1;
 
// Function to find the maximum length
// of a path which forms an AP
vector<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 Code
int 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 approach
class GFG{
 
// Tree Node
static 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 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(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 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);
    System.out.print(ans);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code for the above approach 
 
# Tree Node
class Node:
 
    def __init__(self, d):
        self.data = d
        self.left = self.right = None
 
# Variable to store the maximum path length
ans = 1;
 
# Function to find the maximum length
# of a path which forms an AP
def 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 Tree
root = 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 approach
using 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:

Time Complexity: O(N) where N is number of nodes in the Tree
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!