Binary Search Tree

Binary Search Tree Property

Stored keys must satisfy the binary search tree property.

• y in left subtree of x, then key[y] < key[x].
• y in right subtree of x, then key[y] > key[x].
• The left and right subtree each must also be a binary search tree.

Structure of a node in a BST

Structure of a node in a BST

Implementation of a Binary Search Tree using a composite data structure

Represented by a linked data structure of nodes. root(T) points to the root of tree T.

• Each node contains fields:
• key
• left – pointer to left child: root of left subtree.
• right – pointer to right child : root of right subtree.
• p – pointer to parent. p[root[T]] = NIL (optional).