Binary Search Tree

Optional Node

Collapse Content Show Content

The Tree data structure is used in many different areas of programming. For example, file systems use trees to store directories and files hierarchically. Another common usage of Trees is to sort data, such as in the Binary Search Tree.

Data - Keys and Values

Many types of data consist of keys and values. For example, books (values) in libraries are stored based on their ISBN number (keys) and you can look up topics (keys) in a book index to find the page (value) that the topic is discussed.

Computers also use keys and values to help find information faster. As in the above examples, data is often associated with a key (usually a unique one), which can then be accessed to find the relevant data quickly. For example, a unique ID can be associated, with a book, song, user account, node, module and more. The data is then accessed by looking up the key in a data structure.

Good Data Structure for Storing Data

Depending on the type of data involved, different data structures can be used that allow items to be stored, retrieved and deleted from the structure. The goal of the data structure is to allow these actions to be performed in an optimal manner.

Q: Why can't everything just be stored in unsorted Arrays?
A: Every time you want to retrieve an item, the computer will need to search through the whole array until it find the item.
Q: OK, so keep all the keys in the array sorted, and then find them quickly with Binary Search.
A: This would work if you have unchanging data that just needs to be set up once. However, a sorted array isn't a good choice if you need to add items too, since the whole arrays constantly needs to be shifted around. instead, we can use other structures, such as the Binary Search Tree.

Binary Search Tree

The Binary Search Tree is a a Binary Tree which stores keys in a sorted manner. Every node's key is smaller than all the key's in the node's left subtree and greater than all the key's in the nodes right subtree. Here's an example:

Binary search tree

Search
What steps would you take to find the key n in a binary search tree?

Search Algorithm

Insertion
To insert an item in the tree, you can use the same follow the same principle to find the 'proper place' to place a new Node. Go down the tree until you reach the bottom, and then insert a Node either to the right or to the left.

You can view a Binary Tree in action here. First insert a few different numbers to built the tree. Then Find those items in the Tree.

Accessing Elements in the Tree

Insertion and Search can usually be done very quickly in a binary Tree. The smallest and largest elements in the tree are easy to find. It's simple to go from one element to the next in the tree and to through the entire Tree in order. We saw the pre-order and post-order traversal of trees. To go through a binary tree in order, you use the appropriately named in-order traversal:

inOrder function:

inOrder the left sub-tree of a Node.
Print the node itself.
inOrder the right sub-tree of the Node.

This simple algorithm will print out the tree in order since a binary tree is structured so all elements in the left tree of a node are smaller than it and all elements in the right subtree are greater than it. Click "print" in the above animation to see this process in action.

Challenge

You will be given an list/array of numbers as input. Insert the numbers (in order) one-at-a-time into a binary search tree. Then print out the tree in pre-order.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Previous Next Node

Comments

mike

Aug 18, 9:54 AM

static class Node{
Node left;
Node right;
int key;

    Node(int key){
        this.key = key;
    }
}

static void doStuff(int[] ar){
    Node top = ar2SortedTree(ar);

cont...

    printPreOrder(top);
    System.out.println();
}

static void printPreOrder(Node curr){
    if(curr == null) return;

    System.out.print(curr.key + " ");
    printPreOrder(curr.left);
    printPreOrder(curr.right);
}

static void insertKey(Node curr, int key){
    if(key > curr.key){
        if (curr.right != null){
            insertKey(curr.right, key);
        } else {
            curr.right = new Node(key);
        }
    } else if(key < curr.key){
        if (curr.left != null){
            insertKey(curr.left, key);
        } else {
            curr.left = new Node(key);
        }
    }
}

static Node ar2SortedTree(int[] ar){
    if(ar == null || ar.length == 0){
        return null;
    }

    Node top = new Node(ar[0]);

    for(int i = 1; i < ar.length; i++){
        insertKey(top, ar[i]);
    }

    return top;
}