Binary Trees

A binary tree is often the easiest type of tree structure to build because it has at most two child nodes. We usually call these child nodes left and right.

We add a top node, our first value. The first value is always at the top – and is a special case when creating the tree, as we don’t have to search any child nodes.

From the parent note, we determine the next node. If the node we’re inserting has a value less than the current node’s value, we navigate to the left side child node down it’s branch. If that value is more, it goes on the right side branch.

We keep repeating this process until we find an empty child node branch, and the node will be placed there. If an existing node exists, with the value we are wanting to insert, we have to determine how to handle this special case.

Because we are looking for values less than the current value, or greater than or equal to the current value, it can branch in only one of two ways, hence the binary portion of the name. While it most likely won’t be perfectly balanced, you will see an upside down tree structure start to appear with the various leaf nodes and tree branches connecting them. Thus, the full name, a binary tree.

A worst case scenario is that you insert an already sorted list of data. This would mean that your binary tree would all go down the same line, and essentially be a linked list. However, with a randomized set of data, you will find both inserting and looking up data, to take a fraction of the time that a normal linked list would take to insert into or search through.

Building a Binary Tree in Pseudocode

Class BinaryTree {
    int mainValue = 0; -- this could be a data value, or pointer to another object
    BinaryTree leftNode = null;
    BinaryTree rightNode = null;

    function insertNode(BinaryTree node) {
        if(node.getValue() < this.mainValue) {
            if(this.leftNode == null) {
                this.leftNode = node;
            } else {
                this.leftNode.insertNode(node);
            }
        } else {
            if(this.rightNode == null) {
                this.rightNode = node;
            } else {
                this.rightNode.insertNode(node);
            }
        }
    }
}

Building a Binary Tree in an OOP like Java

Binary Trees was originally found on Access 2 Learn