Skip to main content
Engineering LibreTexts

13.1: A simple MyTreeMap

  • Page ID
    12806
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    In the previous exercise I gave you the outline of MyTreeMap and asked you to fill in the missing methods. Now I’ll present a solution, starting with findNode:

    private Node findNode(Object target) {
        // some implementations can handle null as a key, but not this one
        if (target == null) {
            throw new IllegalArgumentException();
        }
    
        // something to make the compiler happy
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) target;
    
        // the actual search
        Node node = root;
        while (node != null) {
            int cmp = k.compareTo(node.key);
            if (cmp < 0)
                node = node.left;
            else if (cmp > 0)
                node = node.right;
            else
                return node;
        }
        return null;
    }
    

    findNode is a private method used by containsKey and get; it is not part of the Map interface. The parameter target is the key we’re looking for. I explained the first part of this method in the previous exercise:

    • In this implementation, null is not a legal value for a key.
    • Before we can invoke compareTo on target, we have to typecast it to some kind of Comparable. The “type wildcard” used here is as permissive as possible; that is, it works with any type that implements Comparable and whose compareTo method accepts K or any supertype of K.

    After all that, the actual search is relatively simple. We initialize a loop variable node so it refers to the root node. Each time through the loop, we compare the target to node.key. If the target is less than the current key, we move to the left child. If it’s greater, we move to the right child. And if it’s equal, we return the current node.

    If we get to the bottom of the tree without finding the target, we conclude that it is not in the tree and return null.


    This page titled 13.1: A simple MyTreeMap is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?