Last Updated on March 29, 2022 by Ria Pathak
Concepts Used
DFS , Recursion, Hashing
Difficulty Level
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.LinkedList;
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;
Queue<Node> queue = new LinkedList<>();
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextLong();
if (queue.isEmpty()) {
root = createNode(n);
((LinkedList<Node>) queue).add(root);
continue;
}
m = sc.nextLong();
t = ((LinkedList<Node>) queue).peekFirst();
((LinkedList<Node>) queue).pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
((LinkedList<Node>) queue).add(t.left);
if (t.right.value != -1)
((LinkedList<Node>) queue).add(t.right);
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) {
// write your code here
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