Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Binary search tree. Internal representation

Like any other dynamic data structure, BST requires storing of some additional auxiliary data, in order to keep its structure. Each node of binary tree contains the following information:

  • a value (user's data);
  • a link to the left child (auxiliary data);
  • a link to the right child (auxiliary data).
Depending on the size of user data, memory overhead may vary, but in general it is quite reasonable. In some implementations, node may store a link to the parent, but it depends on algorithm, programmer want to apply to BST. For basic operations, like addition, removal and search a link to the parent is not necessary. It is needed in order to implement iterators.

With a view to internal representation, the sample from the overview changes:

binary search tree internal representation
Leaf nodes have links to the children, but they don't have children. In a programming language it means, that corresponding links are set to NULL.

Code snippets

It is a routine, when the whole structure of BST is put into two classes. Main class BinarySearchTree is a public interface and BSTNode mean for private use inside the main class. This division is necessary, because some operations, like removal, may result in an empty tree, which means that tree even doesn't have a root node.

Java

public class BSTNode {

      private int value;

      private BSTNode left;

      private BSTNode right;

 

      public BSTNode(int value) {

            this.value = value;

            left = null;

            right = null;

      }

}

 

public class BinarySearchTree {

      private BSTNode root;

 

      public BinarySearchTree() {

            root = null;

      }

}

C++

class BSTNode {

private:

      int value;

      BSTNode* left;

      BSTNode* right;

public:

      BSTNode(int value) {

            this->value = value;

            left = NULL;

            right = NULL;

      }

};

 

class BinarySearchTree {

private:

      BSTNode* root;

public:

      BinarySearchTree() {

            root = NULL;

      }

};

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++.(Practice)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Partners Ads        Chandeliers and Mirrors        lights        

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: