What could be a better way to find if two (or 'n') particular values are present in a binary tree or not ?

[kapil2905]

Hi ppl :),

I have a solution to find if two values are present in a tree.

I would like to know if there is a
[1] More efficient way to do this ?
[2] More elegant way to this ?
[3] I have mentioned, in comments, the sections of code which I feel could be
done in a better way. Would appreciate suggestions on those sections.
[4] How can we generalize the solution if we have to check if some 'n'
values(all of them) are present in tree or not ?

/*The structure of a Node is as follows:
struct Node {
    int data;
    Node * right, * left;
};*/

void IsPresent(Node* p, int n1, int n2, bool& f1, bool& f2);

bool CheckIfValuesPresentInTree(Node* root, int n1, int n2) {
    auto f1 = bool{false};
    auto f2 = bool{false};

    IsPresent(root, n1, n2, f1, f2);
    
    return f1&&f2;
}

void IsPresent(Node* p, int n1, int n2, bool& f1, bool& f2) {
// Too many arguments passed to the function.
    if (!p) {
        return;
    }
    
    if (p->data == n1) {
        f1 = true;
    }
    
    if (p->data == n2) {
        f2 = true;
    }
   
    IsPresent(p->left, n1, n2, f1, f2);
    IsPresent(p->right, n1, n2, f1, f2);
// Second recursive call might not be needed if both n1 and n2 are found
// in 1st call.
// We can write something like below : but is there a better way ?
/*
    IsPresent(p->left, n1, n2, f1, f2);
    if (f1 && f2) {
        return;
    }
    IsPresent(p->right, n1, n2, f1, f2);
*/
}

[dutch]

If it's really a BST then your algorithm is incorrect. You've written it as if the tree is totally unordered, which means that the entire tree might need to be searched. If it's really a BST then it should just be:

bool contains(Node* t, int n) {
    if (!t) return false;
    if (n == t->data) return true;
    return n < t->data ? contains(t->left, n) : contains(t->right, n);
}

bool constainsBoth(Node* t, int n, int m) {
    return constains(t, n) && contains(t, m);
}

And contains can of course be easily rewritten without recursion.

bool contains(Node* t, int n) {
    while (t) {
        if (n == t->data) return true;
        t = n < t->data ? t->left : t->right;
    }
    return false;
}

I haven't thought about optimizing it for finding two or more values, but you would probably want to sort them first.

[jonnin]

if you need to do a lot of searching and need performance...
you can make sure to keep the tree balanced. trees can degenerate into near lists over time, so a rebalance is critical to keeping the performance.

when making the tree, maybe you should do a little micro memory manager, and get a bunch of nodes at a time, so you have linear blocks of memory for the nodes, such that you don't page fault every time you follow a pointer.

another way to deal is to keep a better data structure off to the side for your quick searches. It would be just a container of pointers to all the nodes... if you really want it to be quick, make some sort of hash table so you can find the value's pointer in O(1)…

[JLBorges]

Why not use std::set (or std:multiset if duplicates are to be allowed)?

For example:

#include <iostream>
#include <set>
#include <algorithm>

template < typename T >
bool is_present( const std::set<T>& tree, const std::set<T>& values ){

    return std::includes( tree.begin(), tree.end(), values.begin(), values.end() ) ;
}

int main() {

    const std::set<int> numbers { 12, 25, 32, 46, 54, 67, 71, 82, 90 } ;
    
    std::cout << std::boolalpha
              << is_present( numbers, { 25, 54, 71, 32, 46 } ) << '\n' // true
              << is_present( numbers, { 25, 53, 71, 32, 46 } ) << '\n' ; // false
}

http://coliru.stacked-crooked.com/a/44e681feb830870b

[kapil2905]

I am extremely sorry for the confusion. It is a simple binary tree and not a bst.
Please note that CheckIfValuesPresentInTree()... Is an api that I need to implement, so I can not change the underlying data structure.

Thanks a lot for taking a look; I would really appreciate any comments specifically to implement a function to check if elements are present in a binary tree.

[JLBorges]

Something like this, perhaps:

#include <iostream>
#include <vector>
#include <set>

struct Node {

    int data = 0 ;
    Node* right = nullptr ;
    Node* left = nullptr ;
};

namespace detail {

    // flags: flags[i] == true if values[i] was found
    // invariant: values.size() <= flags.size()
    // cnt: count of the elements in vector values found so far
    static void IsPresent( const Node* pn, const std::vector<int>& values,
                           std::vector<bool>& flags, std::size_t& cnt )
    {
        for( std::size_t i = 0 ; i < values.size() ; ++i )
            if( pn->data == values[i] ) { flags[i] = true ; ++cnt ; }
        
        if( cnt < values.size() && pn->left ) IsPresent( pn->left, values, flags, cnt ) ;
        if( cnt < values.size() && pn->right ) IsPresent( pn->right, values, flags, cnt ) ;
    }
}

// return vector of flags. flags[i] == true if values[i] is present
std::vector<bool> IsPresent( const Node* pn, const std::vector<int>& values ) {

    std::vector<bool> flags( values.size() ) ; // initialised to all false
    std::size_t cnt = 0 ;
    if(pn) detail::IsPresent( pn, values, flags, cnt ) ;
    return flags ;
}

int main()
{
    Node tree[] { {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10} };

    {
        // build a toy tree for testing
        const auto link = [&tree] ( int i, int r, int l )
                          { tree[i].right = tree+r ; tree[i].left = tree+l ; };
        link( 0, 1, 2 ) ;
        link( 1, 3, 4 ) ;
        link( 2, 5, 6 ) ;
        link( 3, 7, 8 ) ;
        link( 4, 9, 10 ) ;
    }
    
    auto result = IsPresent( tree, { 2, 20, 3, 30, 4, 40, 5, 50, 8, 80, 9 } ) ;
    for( bool f : result ) std::cout << f << ' ' ; // 1 0 1 0 1 0 1 0 1 0 1
    std::cout << '\n' ;

    result = IsPresent( tree, { 0, 6, 5, 2 } ) ;
    for( bool f : result ) std::cout << f << ' ' ; // 1 1 1 1
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/8bc56fa71257b956

[JLBorges]

If the tree is allowed to have duplicate values, modify line 21 to

// if( pn->data == values[i] ) { flags[i] = true ; ++cnt ; }
if( !flags[i] && pn->data == values[i] ) { flags[i] = true ; ++cnt ; }

[jonnin]

so I can not change the underlying data structure.

just to be clear, I was suggesting a second data structure, not a replacement. Leave it in the tree, but cheat a little with something better suited to searching on the side, is an option. Or, the real answer: there isn't any algorithm to find an item in a random tree quickly. A BST is solid if you avoid memory problems and keep it balanced. If that isn't good enough, you may need to look at a redundant side structure that gets the task done, or go have a conversation with whoever gave you the lame requirements. If you can't change anything, you are stuck with a brute force touch every guy algorithm.


you can make an API for a tree without using a tree, ironically. Ive built 'trees' in vectors before.

[kapil2905]

Thanks a lot for your suggestions, @JLBorges, @jonnin & @dutch:)