# Binary Trees and Binary Search Trees

The simplest form of tree is a Binary Tree. A Binary Tree consists of a node (called the root node) and Left and right subtrees. Both the subtrees are themselves binary trees. A node can’t have more than 2 children. A binary tree is called **Full binary tree** if it has all leaves are on the same level and every node has either zero or two children. Similarly, a binary tree is called **complete binary tree**, if its leaves are filled from left to right on one level before moving to next level.

**Skewed binary tree:**Contains only left or right children.**Similar:**Two trees with same structure and different data.**Copy or identical:**Same structure and same data.

struct Node { int data Node *left Node *right }

# Binary Search Trees

When we store ordered data in an array, we have a very efficient search algorithm, i.e. the binary searching. However, we have very inefficient insertion and deletion algorithms that require shifting data in the array. To provide efficient insertions and deletions, we developed the linked list. The problem with linked lists, however, is that their search algorithms are sequential searches, which are very inefficient.

Can we get the best of both worlds (i.e., efficient search, insertion, and deletion algorithms)? The binary search tree is our answer!

The binary search tree is a binary tree with the following properties:

- All items (keys) in the left subtree are less than the root’s key.
- All items (keys) in the right subtree are greater than the root’s key.
- Each subtree is, itself, a binary search tree.

- A binary search tree is a binary tree such that
- For every node X in the tree:
- the values of all the items in its left subtree are smaller than the value of the item in X
- the values of all items in its right subtree are greater than the value of the item in X.

Here you can see the basic structure of a binary search tree.

## Operations on Binary Search Trees

Binary trees offer short paths from root. A node has up to two children. Data is organized by value:

- Insertion
- Search
- Traversal
- Deletion
- Find Minimum: Find the item that has the minimum value in the tree
- Find Maximum: Find the item that has the maximum value in the tree
- Print: Print the values of all items in the tree, using a traversal strategy that is appropriate for the application
- Successor
- Predecessor

A more detailed topic on Operations of Binary Search Trees will be presented later.

### Inserting an item in BST

The first value inserted goes at the root. Every node inserted becomes a leaf. Insert left or right depending upon value.

void Insert(Node *&tree, int item) //’tree’ points to ‘root’ node in // the beginning { if(tree == NULL) { // base case tree = new Node; tree->right = NULL; tree->left = NULL; tree->data = item; } else if(item < tree->data) Insert(tree->left, item); else Insert(tree->right, item); }

**Note:**we have written this definition in a way that ensures that no two entries in a binary search tree can have equal keys. Although it is possible to modify the definition to allow entries with duplicate keys, it makes the algorithms somewhat more complicated. If duplicates need to be accounted for, they can be stored in another data structure (e.g., list).

The binary search tree property does not say what happens with the elements with the same key. In our examples, all the keys will be distinct but in practice it is important to cover the case of multiple elements with the same key (duplicate keys). The duplicate keys can all be kept in the left subtree, or all in the right subtree. It doesn’t matter which we choose, but it matters that the choice is the same for the whole implementation. Another issue: with duplicate keys, it is important to have extra operations in the interface: getAll, and removeAll

### Related Posts

- Heap data structure in C++
- Binary Search Trees and Data Structure
- Introduction to Tree Data Structure
- Operations on Binary Search Trees (BST)
- Binary Expression Trees
- Advanced Data Structures Tutorial using C++
- Circular Linked Lists
- Graph search in C++
- Graph Implementation in C++
- Doubly Linked Lists
- Data Structures Tutorial using C++
- Selection Sort: A Graphical Explanation

### Popular Posts (last 30 days)

- Applications of Stack in … 1071 view(s)
- Circular Linked Lists 1035 view(s)
- Attendance Management Sys… 870 view(s)
- Simple Currency Converter… 646 view(s)
- Recursive Factorial funct… 568 view(s)
- Implementing Stack Data S… 541 view(s)
- Graph Implementation in C… 490 view(s)
- Finding Minimum, Maximum … 423 view(s)
- Finding Maximum Number in… 295 view(s)
- GRASP Design Patterns 291 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books