Binary Search Tree Node Lookup

Binary search trees do not have indices, so for the lookup operation in a binary search tree, a contain method is defined here to check if the binary search tree contains a specific element, returning a boolean variable. This lookup operation is also a recursive process. The specific code implementation is as follows:

...
// Check if the binary search tree rooted at node contains a node with the key, using a recursive algorithm
private boolean contain(Node node, Key key){

    if( node == null )
        return false;

    if( key.compareTo(node.key) == 0 )
        return true;
    else if( key.compareTo(node.key) < 0 )
        return contain( node.left , key );
    else // key > node->key
        return contain( node.right , key );
}
...

The following example searches for the element 43 in the binary search tree:

(1) Element 43 is greater than the root node 42, so comparison continues in the right child node.

(2) Element 43 is smaller than 59, so comparison continues in the left child node.

(4) Searching the left child node 43 of 51, which is equal, so the search ends.

If you need to find the value corresponding to a key, the code is as follows:

...
// Search for the value corresponding to key in the binary search tree rooted at node, using a recursive algorithm
// If the value does not exist, return NULL
private Value search(Node node, Key key){

    if( node == null )
        return null;

    if( key.compareTo(node.key) == 0 )
        return node.value;
    else if( key.compareTo(node.key) < 0 )
        return search( node.left , key );
    else // key > node->key
        return search( node.right, key );
}
...

Java Example Code

Source Code Download: Download

src/tutorialpro/binary/BinarySearchTreeSearch.java File Code:

package tutorialpro.binary;

/**
 * Binary Search Tree Lookup
 */
public class BinarySearchTreeSearch&lt;Key extends Comparable<Key>, Value> {
    // Nodes in the tree are private classes, and the specifics of the binary search tree node implementation are not needed by the outside world
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // Root node
    private Node root;
    // Number of nodes in the tree
    private int count;

    // Constructor, default to an empty binary search tree
    public BinarySearchTreeSearch() {
        root = null;
        count = 0;
    }

    // Return the number of nodes in the binary search tree
    public int size() {
        return count;
    }

    // Return whether the binary search tree is empty
    public boolean isEmpty() {
        return count == 0;
    }

    // Insert a new (key, value) data pair into the binary search tree
    public void insert(Key key, Value value){

root = insert(root, key, value);
}

// Check if the binary search tree contains the key
public boolean contain(Key key) {
    return contain(root, key);
}

// Search for the value corresponding to the key in the binary search tree. If it does not exist, return null
public Value search(Key key) {
    return search(root, key);
}

//********************
//* Auxiliary functions for the binary search tree
//********************

// Insert node (key, value) into the binary search tree rooted at node using a recursive algorithm
// Return the root of the binary search tree after inserting the new node
private Node insert(Node node, Key key, Value value) {

    if (node == null) {
        count++;
        return new Node(key, value);
    }

    if (key.compareTo(node.key) == 0)
        node.value = value;
    else if (key.compareTo(node.key) < 0)
        node.left = insert(node.left, key, value);
    else // key > node.key
        node.right = insert(node.right, key, value);

    return node;
}

// Check if the binary search tree rooted at node contains a node with key using a recursive algorithm
private boolean contain(Node node, Key key) {

    if (node == null)
        return false;

    if (key.compareTo(node.key) == 0)
        return true;
    else if (key.compareTo(node.key) < 0)
        return contain(node.left, key);
    else // key > node.key
        return contain(node.right, key);
}

// Search for the value corresponding to the key in the binary search tree rooted at node using a recursive algorithm
// If the value does not exist, return null
private Value search(Node node, Key key) {

    if (node == null)
        return null;

    if (key.compareTo(node.key) == 0)
        return node.value;
    else if (key.compareTo(node.key) < 0)
        return search(node.left, key);
    else // key > node.key
        return search(node.right, key);
}