CS 70

C++ Implementation: Exists

Here's how our class declaration would change with the addition of an exists member function and its private helper function.

class IntTree {
  public:
    void insert(int k);
    bool exists(int k) const;
    ...

  private:
    struct Node {
        ...
    };
    Node* root_;

    static void insertHelper(Node*& tree, int k);
    static bool existsHelper(const Node* tree, int k);
};

Notice that we're no longer needing to do any of that Node*& stuff, as exists doesn't need to update pointers in the tree. We do, however, have some added const keywords reflecting the fact that we won't be changing the tree.

Is there anything fundamentally new/different about the code to implement exists compared to insert?

  • Hedgehog speaking

    Phew!

  • LHS Cow speaking

    Yeah, you got this!

  • Goat speaking

    Hang on, I bet that means you're not going to give us any code for these functions.

  • LHS Cow speaking

    You're catching on!

  • RHS Cow speaking

    You'll get to write this code as part of the assignment.

  • Duck speaking

    Can I write exists non-recursively (and maybe avoid writing existsHelper at all)?

  • LHS Cow speaking

    In principle, yes, you could. But in the code you write for your homework, no. We require you to implement both insert and exists using a recursive helper function.

  • Duck speaking

    Why? The recursive code won't be as efficient!

  • LHS Cow speaking

    Without testing, you can't know it won't be as efficient. In fact, with a modern compiler it'll likely be about the same.

  • RHS Cow speaking

    Trees are an inherently recursive encoding. Writing recursive code to deal with that encoding results in the clearest code for other people to follow.

(When logged in, completion status appears here.)