# Implementation

A binary tree has a natural implementation in linked storage. A separate pointer is used to point the tree (e.g. root)

root = NULL; // empty tree

Each node of a binary tree has both left and right subtrees which can be reached with pointers:

struct tree_node{

int data;

struct tree_node *left_child;

struct tree_node *right_child;

};

Binary Search Tree:-

BST is a binary tree. For each node in a BST, the left subtree is smaller than it; and the right subtree is greater than it. A **binary search tree** (**BST**), sometimes also called an **ordered** or **sorted binary tree**, is a node-based binary tree data structure which has the following properties:

- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree must each also be a binary search tree.
- There must be no duplicate nodes.

**Implementation**

We implement a binary search tree using a private inner class BSTNode. In order to support the *binary search tree property*, we require that data stored in each node is Comparable:

public class BST <AnyType extends Comparable<AnyType>>

{

private Node<AnyType> root;

private class Node<AnyType>

{

private AnyType data;

private Node<AnyType> left, right;

public Node(AnyType data)

{

left = right = null;

this.data = data;

}

}

...

Insertion

The insertion procedure is quite similar to searching. We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.

**
Example:** Given a sequence of numbers:

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

Draw a binary search tree by inserting the above numbers from left to right.

**Searching**

Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for (let us call it as **to Search**). If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive algorithm.

Deletion

Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted (let us call it as **to Delete**)

- is not in a tree;
- is a leaf;
- has only one child;
- has two children.

If **to Delete** is not in the tree, there is nothing to delete. If **to Delete** node has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two subtrees and therefore, some children of the internal node won’t be accessible after deletion. In the picture below we delete 8:

Deletion starategy is the following: replace the node being deleted with the largest node in the left subtree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right subtree.

Binary Heaps

A binary tree is **completely full** if it is of height, *h*, and has 2^{h}^{+1}-1 nodes.

A binary tree of height, *h*, is **complete** *iff*

a. it is empty *or*

b. its left sub tree is complete of height *h*-1 and its right sub tree is completely full of height *h*-2 *or*

c. Its left sub tree is completely full of height *h*-1 and its right sub tree is complete of height *h*-1.

A complete tree is filled from the left:

❖ all the leaves are on

• the same level *or*

• two adjacent ones *and*

❖ All nodes at the lowest level are as far to the left as possible.