Maximum Distinct

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 referred from the best websites to learn coding.

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);

    }

}

Previous post Mirror Tree
Next post Height of Tree

Leave a Reply

Your email address will not be published. Required fields are marked *