In a binary tree, every node can have a maximum of two children but there is no need to maintain the order of nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the tree from top to bottom and left to right.

A binary tree has the following time complexities...

1.Search Operation - O(n)

2.Insertion Operation - O(1)

3.Deletion Operation - O(n)

To enhance the performance of binary tree, we use a special type of binary tree known as Binary Search Tree. Binary search tree mainly focuses on the search operation in a binary tree. Binary search tree can be defined as follows...

1. BST Definition: Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.

Binary Search 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 lesser 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 each must also be a binary search tree.
- There must be no duplicate nodes.

AbstractDataType BSTree

{

Instances: Binary tree, each node has an element with a key field; all keys are distinct; keys in the left subtree of

any node are smaller than the key in the root node; those in the right subtree are larger.

Operations:

Create(): Creates an empty binary search tree.

BuildTree(root,left,right): creates a binary search tree with root as the root element, left a left subtree, and right

as right subtree.

Preorder(visit): preorder travels of binary search tree.

Inorder(visit): Inorder travels of binary search tree.

postorder(visit): postorder travels of binary search tree.

Levelorder(visit): level order travels of binary search tree.

search(k,e): return in ‘e’ the element with ‘k’ return false if the operation fails, return tree if it succeeds.

}

## 0 comments :

## Post a Comment

Note: only a member of this blog may post a comment.