0
\$\begingroup\$

I have a solution to find if two values are present in a binary tree (not a BST).

I would like to know if there is

  1. a more efficient way to do this?
  2. a more elegant way to this?
  3. specific improvement for the parts I've marked with comments?
  4. a better way to generalize the solution if we have to check if some 'n' values (all of them) are present in tree or not?

I have a working solution mentioned in the code below but I think the same could be achieved using a more elegant and efficient code.

Note : Please assume that CheckIfValuesPresentInTree() is an API that I need to implement, so I can't change the underlying data structure.

/*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);
*/
}
\$\endgroup\$
2
\$\begingroup\$

Reading the title, you want a solution that covers N values. Looking at your code, it doesn't meet that expectation. Not do I see you writing all variants from 1 to N.

As API, you have 2 options: compile time N or runtime. If you go for the compile time, use variadic templates in the call. Otherwise, go for std::vector. As I always mess up the ..., I'll continue with the vector.

Your current approach makes good use of cache locality. Really interesting if the tree is big. Alternatively, you could check each element 1 by 1, really good for a big number of values if you expect a lot of miss matches.

What I would suggest is the following:

bool CheckIfValuesPresentInTree(Node* root, const std::vector<int> & n) {
     auto f = std::vector<bool>{};
    f.resize(n.size(), false);
    IsPresent(root, n, f);

    return std::all_of(f.cbegin(), f.cend());
}

void IsPresent(Node* p, const std::vector<int> &n, std::vector<bool> &f) {

    if (!p) {
        return;
    }

    for (size_t i = 0; i < n.size(); ++i)
    {
      if (p->data == n[I]) 
           f[I] = true;
    }

    IsPresent(p->left, n, f);
    IsPresent(p->right, n, f);
}

About your question on whether to stop searching once everything if found. Ain't an easy question, given the existing API, I wouldn't bother as it might be more expensive to check.

It can however be done by changing the way you indicate if the value is found. Instead of using the bool, you could use the n to keep track of values you still need to search.

void IsPresent(Node* p, std::vector<int> &n) {

    if (!p) {
        return;
    }

    for (auto it = n.cbegin(); it != n.cend(); /**/)
    {
      if (p->data == *it) 
           it = n.erase(it);
     else
           ++it;
    }

    if (n.empty())
        return;

    IsPresent(p->left, n);

    if (n.empty())
         return;
    IsPresent(p->right, n);
}

The advantage of this, is that the amount of values you are checking reduces while searching. The check on whether you need to terminate becomes really cheap, at the expense of some bookkeeping.

\$\endgroup\$
1
\$\begingroup\$

I have a solution to find if two values are present in a binary tree (not a bst).

Why not use a BST? If you find yourself trying to hammer a square peg into a round hole, you should take a step back and see whether you can use a round peg or a square hole.


[1] More efficient way to do this ?
[2] More elegant way to this ?

Write code to search for a single item in a tree, aborting early when you find it, and call it twice.


[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 ?

Turn the tree into a std::unordered_set and then test each value against the set.

\$\endgroup\$
  • \$\begingroup\$ Please note that I have already mentioned that CheckIfValuesPresentInTree().. is an api and I am not allowed to change underlying data structure. \$\endgroup\$ – kapil Jan 29 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.