Longest Univalue Path

Problem Source: LeetCode
Companies: Amazon, Apple

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

          5
         / \
        4   5
       / \   \
      1   1   5

Output: 2

Solution

We will use recursion to compute the longest univalue path. We will make a recursive function called length, which will compute the longest univalue path in the left subtree and the longest univalue path in the right subtree.

Implementation

// C++ program to find the Longest Univalue Path
#include <bits/stdc++.h>
using namespace std;

typedef struct Node {
  int val;
  struct Node *left, *right;
} Node;

/**
This computes the longest univalue path for the subtree of node
*/
int length(Node *node, int *ans) {
  if (node == NULL)
    return 0;

  /** Longest univalue path in left subtree */
  int left = length(node->left, ans);
  /** Longest univalue path in right subtree */
  int right = length(node->right, ans);

  int leftMax = 0, rightMax = 0;

  /** If the left node exists and is equal to current node, then set the leftMax */
  if (node->left && node->left->val == node->val)
    leftMax += left + 1;

  /** If the right node exists and is equal to current node, then set the rightMax */
  if (node->right && node->right->val == node->val)
    rightMax += right + 1;

  *ans = max(*ans, leftMax + rightMax);

  return max(leftMax, rightMax);
}

int longestSameValuePath(Node *root) {
  int ans = 0;
  length(root, &ans);
  return ans;
}

Node *newNode(int data) {
  Node *temp = new Node;
  temp->val = data;
  temp->left = temp->right = NULL;
  return temp;
}

// Driver code
int main() {
  /* Let us construct a Binary Tree
        5
       / \
      4   5
     / \   \
    1   1   5 */

  Node *root = NULL;
  root = newNode(5);
  root->left = newNode(4);
  root->right = newNode(5);
  root->left->left = newNode(1);
  root->left->right = newNode(1);
  root->right->right = newNode(5);
  cout << longestSameValuePath(root);
  return 0;
}