Article 107 - Binary Search Tree Implementation

This article discusses the implementation of a binary tree with the requirement of binary search.

Implementation of a binary search is really simple. At each node, compare the value of the search request to the node's value, if there is a match, return the node.

Otherwise, traverse the left child or the right child depending which side the node should be contained in, which depends if the search value is less than or greater than the current node's value..

One property to remember is that all nodes root by the right child node is strictly larger than the current node's value. All nodes rooted by the left child node is strictly smaller than the current node's value.

Binary Search Tree Node structure used in the implementation.

typedef struct Node {
    struct Node * leftChild;
    struct Node * rightChild;
    int content;
} Node;

Binary Search implementation.

Node * binarySearch( Node * tree, int search ){
    Node * nodePointer;

    if( !tree ){
        return 0;
    }
   
    for( nodePointer = tree; nodePointer;  ){
        if( nodePointer->content == search ){
            return nodePointer;
        }
        else if( search < nodePointer->content ){
            nodePointer = nodePointer->leftChild;
        }
        else{
            nodePointer = nodePointer->rightChild;
        }
    }

    return 0;   
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.