Binary Search Trees
Data Structures: A Pseudocode Approach with C, Second Edition 1
A Binary Search Tree is a binary
tree with the following properties:
All items in the left subtree are less than
the root.
All items in the right subtree are greater
or equal to the root.
Each subtree is itself a binary search tree.
Data Structures: A Pseudocode Approach with C, Second Edition 2
Basic Property
In a binary search tree,
the left subtree contains key values less
than the root
the right subtree contains key values
greater than or equal to the root.
Data Structures: A Pseudocode Approach with C, Second Edition 3
Data Structures: A Pseudocode Approach with C, Second Edition 4
(a), (b) - complete and balanced trees;
(d) – nearly complete and balanced tree;
(c), (e) – neither complete nor balanced trees,
left & right skewed trees
Data Structures: A Pseudocode Approach with C, Second Edition 5
Data Structures: A Pseudocode Approach with C, Second Edition 6
BST Operations
Four basic BST operations:
• Traversals
• Searches
• Insertion
• Deletion
Data Structures: A Pseudocode Approach with C, Second Edition 7
Data Structures: A Pseudocode Approach with C, Second Edition 8
Data Structures: A Pseudocode Approach with C, Second Edition 9
Preorder Traversal
23 18 12 20 44 35 52
Data Structures: A Pseudocode Approach with C, Second Edition 10
Postorder Traversal
12 20 18 35 52 44 23
Data Structures: A Pseudocode Approach with C, Second Edition 11
Inorder Traversal
12 18 20 23 35 44 52
Inorder traversal of a binary search tree produces a
sequenced list in ascending order
Data Structures: A Pseudocode Approach with C, Second Edition 12
Right-Node-Left Traversal
52 44 35 23 20 18 12
Right-node-left traversal of a binary search tree produces a
descending sequence
Data Structures: A Pseudocode Approach with C, Second Edition 13
Three BST search algorithms:
Find the smallest node
Find the largest node
Find a requested node
Data Structures: A Pseudocode Approach with C, Second Edition 14
Data Structures: A Pseudocode Approach with C, Second Edition 15
Data Structures: A Pseudocode Approach with C, Second Edition 16
Data Structures: A Pseudocode Approach with C, Second Edition 17
Data Structures: A Pseudocode Approach with C, Second Edition 18
Data Structures: A Pseudocode Approach with C, Second Edition 19
Data Structures: A Pseudocode Approach with C, Second Edition 20
BST Insertion
To insert data all we need to do is follow
the branches to an empty subtree and
then insert the new node.
In other words, all inserts take place at a
leaf or at a leaflike node – a node that has
only one null subtree.
Data Structures: A Pseudocode Approach with C, Second Edition 21
Data Structures: A Pseudocode Approach with C, Second Edition 22
Data Structures: A Pseudocode Approach with C, Second Edition 23
Data Structures: A Pseudocode Approach with C, Second Edition 24
30 30
30 30
Data Structures: A Pseudocode Approach with C, Second Edition 25
Creating a BST
Given sequence:
11,6,8,19,4,10,5,17,43,49,31
Data Structures: A Pseudocode Approach with C, Second Edition 26
Creating a BST
Given sequence:
11,6,8,19,4,10,5,17,43,49,31
Data Structures: A Pseudocode Approach with C, Second Edition 27
Exercise
Create a BST for the given sequence:
12,16,4,9,7,12,5,11,42,40,36
Note: Two identical keys
Data Structures: A Pseudocode Approach with C, Second Edition 28
Deletion
The following are possible cases when we delete a node:
The node to be deleted has no children. In this case, all
we need to do is delete the node.
The node to be deleted has only a right subtree. We
delete the node and attach the right subtree to the
deleted node’s parent.
The node to be deleted has only a left subtree. We
delete the node and attach the left subtree to the
deleted node’s parent.
The node to be deleted has two subtrees. It is possible
to delete a node from the middle of a tree, but the result
tends to create very unbalanced trees.
Data Structures: A Pseudocode Approach with C, Second Edition 29
Deletion from the middle of a tree
Rather than simply delete the node, we
try to maintain the existing structure as
much as possible by finding data to take
the place of the deleted data. This can be
done in one of two ways.
Data Structures: A Pseudocode Approach with C, Second Edition 30
Deletion from the middle of a tree
We can find the largest node in the
deleted node’s left subtree and move its
data to replace the deleted node’s data.
We can find the smallest node on the
deleted node’s right subtree and move its
data to replace the deleted node’s data.
Either of these moves preserves the
integrity of the binary search tree.
Data Structures: A Pseudocode Approach with C, Second Edition 31
Data Structures: A Pseudocode Approach with C, Second Edition 32
(continued)
Data Structures: A Pseudocode Approach with C, Second Edition 33
27 27
27 27
Data Structures: A Pseudocode Approach with C, Second Edition 34
Data Structures: A Pseudocode Approach with C, Second Edition 35
Data Structures: A Pseudocode Approach with C, Second Edition 36
Exercise
Show the two possible BSTs after removing
the root.
Data Structures: A Pseudocode Approach with C, Second Edition 37
Data Structures: A Pseudocode Approach with C, Second Edition 38
Binary Search Tree ADT
Data Structures: A Pseudocode Approach with C, Second Edition 39
Data Structures: A Pseudocode Approach with C, Second Edition 40
Data Structures: A Pseudocode Approach with C, Second Edition 41
Application – Student data processing
Data Structures: A Pseudocode Approach with C, Second Edition 42
Gets choice of operation
Adds a student
Deletes a student
Search for a student
Prints the complete list
Compares 2 studs
Prints a student record
Data Structures: A Pseudocode Approach with C, Second Edition 43
Threaded trees
• If the tree is traversed frequently, threaded
trees are useful
• Null pointers are replaced with pointers to
successor nodes
• Avoids using stack for recursion otherwise
Data Structures: A Pseudocode Approach with C, Second Edition 44
Threaded trees
Considering the Inorder traversal,
Data Structures: A Pseudocode Approach with C, Second Edition 45
Conversion to Threaded trees
Data Structures: A Pseudocode Approach with C, Second Edition 46
Exercise
Conversion to Threaded trees
Data Structures: A Pseudocode Approach with C, Second Edition 47
