Binary Search tree O(log n)

Page 1

Binary Search Tree :

Property :

Any node in the tree must have lower in the left sub tree and higher values in the right sub tree.

Basic operations include:

SEARCH

MINIMUM

MAXIMUM

PREDECESSOR

SUCCESSOR

INSERT

DELETE.

Can be represented using double linked list :

Key (node)

left

right

Tree traversals:

Inorder = print (left keys, root, right keys)

Preorder = print(root, left keys, right keys)

Postorder = print(left keys, right keys, root)

Page 2