Page 244 - DCAP407_DATA_STRUCTURE

Unit 13: Binary Search Trees

We use binary search trees for applications such as searching, sorting, and in–order
traversal.

13.1 Binary Search Tree Operations
The four main operations that we perform on binary trees are:
1. Searching
2. Insertion

3. Deletion
4. Traversal
13.1.1 Searching in Binary Search Trees
In searching, the node being searched is called as key node. We first match the key node with the root
node. If the value of the key node is greater than the current node, then we search for it in the right sub-
tree, else we search in the left sub-tree. We continue this process until we find the node or until no
nodes are left. The pseudo code for searching a binary search tree is as follows:
Pseudocode for a Binary Search Tree
find(X, node){
if(node = NULL)
return NULL
if(X = node:data)
return node

else if(X<node:data)
return find(Y,node:leftChild)
else if(X>node:data)
return find(X,node:rightChild)
}

Figure 13.3: Binary Search Tree

LOVELY PROFESSIONAL UNIVERSITY 237