Write the algorithmic steps for searching a binary search tree.
Ans. A binary tree that has the property that all elements in the left subtree of a node n are less than the contents of n, and all the elements in the right subtree of n are greater than or equal to the contents of n is called a binary search tree. If a binary search tree is traversed in inorder and the contents of each node are printed as the node is visited, the numbers are printed in ascending order. Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
The algorithm for searching for the key in a binary search tree is as follows;
Each node contains four fields: k which holds the record’s key value, r, which holds the record itself, and left and right, which are pointers to the sub trees.
p = tree; while ( p!= null && key!= k(p)) p = ( key < k(p)) ? left(p) :right(p): return(p);