Longest Arithmetic Sequence Tree Path - Google Top Interview Questions

                        Solution in C++ :

int maxS = 0;
void dfs(Tree* root, int diff, int l) {
    maxS = max(maxS, l);
    if (!root) {
        return;
    }
    if (root->left) {
        if (root->left->val - root->val == diff) {
            dfs(root->left, diff, l + 1);
        } else {
            dfs(root->left, root->left->val - root->val, 2);
        }
    }
    if (root->right) {
        if (root->right->val - root->val == diff) {
            dfs(root->right, diff, l + 1);
        } else {
            dfs(root->right, root->right->val - root->val, 2);
        }
    }
}
int solve(Tree* root) {
    if (root) {
        maxS = 1;
    } else {
        return 0;
    }
    dfs(root, 0, 1);
    return maxS;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */

class Solution {
    int ans;

    public int solve(Tree root) {
        if (root == null) {
            return 0;
        }

        ans = 1;
        sol(root);
        return ans;
    }

    HashMap<Integer, Integer> sol(Tree root) {
        if (root == null) {
            return new HashMap<>();
        }

        HashMap<Integer, Integer> l = sol(root.left);
        HashMap<Integer, Integer> r = sol(root.right);

        HashMap<Integer, Integer> mp = new HashMap<>();

        if (root.left != null) {
            int ldiff = root.val - root.left.val;
            int x = l.getOrDefault(ldiff, 1);
            int y = mp.getOrDefault(ldiff, 1);
            mp.put(ldiff, Math.max(x + 1, y));
            ans = Math.max(ans, mp.get(ldiff));
        }

        if (root.right != null) {
            int rdiff = root.val - root.right.val;
            int x = r.getOrDefault(rdiff, 1);
            int y = mp.getOrDefault(rdiff, 1);
            mp.put(rdiff, Math.max(x + 1, y));
            ans = Math.max(ans, mp.get(rdiff));
        }

        return mp;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    # global ans to use same solve function for recursion 😅
    ans = 0
    # diff is diffrence of cur value with prev to check airth seq
    # ltill is longest airth seq ending before cur node
    def solve(self, cur, ltill=0, diff=None):
        # Intialize a global ans ans is max of prev longest airthmetic seq and cur longest
        self.ans = max(self.ans, ltill)
        # Check if ther is left child
        if cur.left:
            # compute diff with left child
            ldiff = cur.left.val - cur.val
            self.solve(
                cur.left,
                # if diff with previous child is diffrent
                # from diff of cur from par
                # or it's root new airthmetic sequence
                # start from here so ltill is 1
                # else extend prev max length ltill by 1
                1 if diff == None or ldiff != diff else ltill + 1,
                ldiff,
            )
        # same for right
        if cur.right:
            rdiff = cur.right.val - cur.val
            self.solve(cur.right, 1 if diff == None or rdiff != diff else ltill + 1, rdiff)

        # we start count from 0 so +1 solve single legth seq also
        return self.ans + 1