Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Maximum Distinct

Last Updated on March 29, 2022 by Ria Pathak

### Concepts Used

DFS , Recursion, Hashing

Hard

### Problem Statement :

Given a binary tree, our task is to return the maximum count of distinct integers present in a path from starting point to ending point.

See original problem statement here

### Solution Approach :

#### Introduction :

We have to traverse, and we can store root to leaf node path, then calculate the distinct values in the path and return the maximum value.

#### Method 1 (Brute Force) :

Although introduction says it all, we can try thinking of a approach of storing all root (making every node a root node one-by-one) to leaf path.
Then we will recursively call the left & right subtrees & store their root to leaf path in a path array.
We can count the distinct values present in each path array , then finally return the value which is maximum.

Below is the implementation of this aproach.

#### Method 2 (Efficient) :

The above approach we have discussed is not very efficient in terms of time. We can reduce the time complexity by storing the values in a single hash instead of path arrays for every root.

We will recursively call left & right subtree and maintain the maximum count for each node using hashing and return the maximum value.

(See C++ implementation)

### Complexity Analysis :

In second method, we are traversing every node and storing distinct nodes in a set. This method has time complexity `O(n)`.

Space complexity is `O(n)`, for the set we are using.

### SOLUTIONS:

```#include <stdio.h>

#include<stdlib.h>

#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)

struct nodelist

{

ll value;

struct nodelist *left;

struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

int front, rear, size;

unsigned capacity;

node* *array;

};

typedef struct Queue queue;

queue* createQueue(unsigned capacity)

{

queue* qu =(queue*)malloc(sizeof(queue));

qu->capacity = capacity;

qu->front = qu->size =0;

qu->rear = capacity-1;

qu->array = (node **)malloc(qu->capacity * sizeof(node));

return qu;

}

int isFull(queue*  queue1)

{

return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

return (queue1->size==0);

}

void enqueue(queue* queue1, node* item)

{

if(isFull(queue1))

return ;

queue1->rear = (queue1->rear +1 )%queue1->capacity;

queue1->array[queue1->rear] = item;

queue1->size = queue1->size +1;

}

node dequeue(queue* queue1)

{

node* item = queue1->array[queue1->front];

queue1->front = (queue1->front +1)%queue1->capacity;

queue1->size = queue1->size -1;

return *item;

}

node* front(queue* queue1)

{

return queue1->array[queue1->front];

}

node* rear(queue * queue1)

{

return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

node *t= (node *) malloc(sizeof(node));

t->value = value;

t->right = t->left = NULL;

return  t;

}

void deleteNode(node*t)

{

free(t);

}

node *replaceNegativeOne(node *root)

{

if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

void deleteTree(node *node1)

{

if(node1==NULL)

return;

deleteTree(node1->left);

deleteTree(node1->right);

free(node1);

}

node *createTreeByLevelTree()

{

ll n,m;

queue* queue1 = createQueue(100000);

node *root, *t;

root = NULL;

while(scanf("%lld", &n))

{

if(isEmpty(queue1))

{

root= createNode(n);

enqueue(queue1,root);

continue;

}

scanf("%lld", &m);

t = front(queue1);

dequeue(queue1);

t->left =createNode(n);

t->right=createNode(m);

if(t->left->value !=-1)

enqueue(queue1,t->left);

if(t->right->value !=-1)

enqueue(queue1,t->right);

if(isEmpty(queue1))

break;

}

return root;

}

void print(node *root,int path[],int n,int *sum)
{
if(root==NULL)
return;
path[n] = root->value;
n +=1;
if(root->left==NULL && root->right==NULL)
{
int count =0,hash[1000]={0};
//static int sum = 0;
//sort(path,path+n);
for(int i=0;i<n;i++)
{
hash[path[i]]++;
if(hash[path[i]]==1)
count++;

}
if(*sum<count)
*sum = count;//cout<<"here";
//cout<<*sum<<endl;
//cout<<count<<endl;
}
else{
print(root->right,path,n,sum);
print(root->left,path,n,sum);
}
}

int findDistinctCount(node* node)
{
int path[64];
int sum = 0;
print(node,path,0,&sum);
return sum;
}

int main() {

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

printf("%d\n", findDistinctCount(root));

deleteTree(root);

return 0;

}

```
```
#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

ll value;

node *left;

node *right;

};

node *createNode(ll value)

{

node *t = new node();

t->value = value;

t->right = t->left = NULL;

return t;

}

void deleteNode(node *t)

{

delete t;

}

node *replaceNegativeOne(node *root)

{

if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

node *createTreeByLevelTree()

{

ll n, m;

queue<node *> q;

node *root, *t;

root = NULL;

while (cin >> n)

{

if (q.empty())

{

root = createNode(n);

q.push(root);

continue;

}

cin >> m;

t = q.front();

q.pop();

t->left = createNode(n);

t->right = createNode(m);

if (t->left->value != -1)

{

q.push(t->left);

}

if (t->right->value != -1)

{

q.push(t->right);

}

if (q.empty())

{

break;

}

}

return root;

}

void deleteTree(node *node)

{

if (node == NULL)

return;

deleteTree(node->left);

deleteTree(node->right);

delete node;

}

int print(node *root,set<long long> m)

{

if(root==NULL)

return m.size();

m.insert(root->value);

int maxpath = max( print(root->left,m),print(root->right,m) );

m.erase(m.find(root->value));

return maxpath;

}

int findDistinctCount(node* node)

{

set<long long> s;

return print(node,s);

}

int main()

{

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

cout<<findDistinctCount(root)<<endl;

deleteTree(root);

return 0;

}
```
```

import java.util.*;

import java.util.Scanner;

import java.io.*;

class Node

{

long value;

Node left, right;

public Node(long item)

{

value = item;

left = right = null;

}

}

class BinaryTree {

Node root;

BinaryTree() {

root = null;

}

Node createNode(long value) {

Node t = new Node(value);

return t;

}

Node replaceNegativeOne(Node root) {

if (root == null || (root.value == -1 && root.left == null && root.right == null)) {

return null;

}

root.left = replaceNegativeOne(root.left);

root.right = replaceNegativeOne(root.right);

return root;

}

Node createTreeByLevelTree() {

Scanner sc = new Scanner(System.in);

long n, m;

Node t;

root = null;

while (sc.hasNext()) {

n = sc.nextLong();

if (queue.isEmpty()) {

root = createNode(n);

continue;

}

m = sc.nextLong();

t.left = createNode(n);

t.right = createNode(m);

if (t.left.value != -1)

if (t.right.value != -1)

if (queue.isEmpty())

break;

}

return root;

}

void deleteTree(Node node) {

node = null;

}

static int printt(Node node, HashMap<Long,Integer> m)
{

if (node == null)
return m.size();

if(m.containsKey(node.value))
{
m.put((node.value), m.get(node.value) + 1);
}
else
{
m.put(node.value, 1);
}

int max_path = Math.max(printt(node.left, m),
printt(node.right, m));

if(m.containsKey(node.value))
{
m.put(node.value, m.get(node.value) - 1);
}

if (m.get(node.value) == 0)
m.remove(node.value);

return max_path;
}

int findDistinctCount(Node node)
{
HashMap<Long,Integer> hash = new HashMap<Long,
Integer>();
return printt(node,hash);
}

}

public class Main {

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

bt.root = bt.createTreeByLevelTree();

bt.root = bt.replaceNegativeOne(bt.root);

System.out.println(bt.findDistinctCount(bt.root));

bt.deleteTree(bt.root);

}

}
```

[forminator_quiz id="1671"]

This article tried to discuss the concept of DFS,Recursion, Hashing. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming