binary Search Tree

Bodhak binary search tree tutorial in this chapter we will discuss Binary Search Tree of Data structures.

Binary Search Trees: A binary search tree is a binary tree with a  special property called the BST-property

which is given as follows: For all nodes x and y, if y belongs to the left subtree of x, then the key at y is less

then the key at x, and if y belongs to the right subtree of x, then the key at y is greater than the key at x.

 

binary search tree

We will assume that the keys of a BST are pairwise distinct.

Each node has the following attributes:

p left, and right, which are pointers to the parent, the left child, and the right child,

respectively,

And the key, which is key stored at the node.

Traversal of the Nodes:

  1. In order. The ordering is the left sub tree, the current node, the right sub tree.
  2. Preorder. The ordering is the current node, the left sub tree, the right sub tree.
  3. Postorder. The ordering is the left sub tree, the right sub tree, the current node.

RLR – Preorder  LRR’ – Postorder     LR’R – In order

Searching for a key:

We assume that a key and the subtree in which the key is searched for are given as an input. We’ll take the full advantage of the BST-property.

Suppose we are at a node. If the node has the key that is being searched for, then the search is over. Otherwise, the key at the current node is either strictly smaller than the key that is searched for or strictly greater than the key that is searched for. If the former is the case, then by the BST property, all the keys in the left subtree are strictly less than the key that is searched for. That means that we do not need to search in the left subtree. Thus, we will examine only the right subtree. If the latter is the case, by symmetry we will examine only the right subtree.