Recursive Version
Data Structures and Algorithms
(DSA)
Lecture 10: Binary Search Trees
Data Structures and Algorithms
Overview
• Trees
• Sorted Sequences
• Binary Search Trees
Data Structures and Algorithms
Tree
Data Structures and Algorithms
7
3 13
2 11
17
19
5
18 22
Representing Trees
• Heaps are special trees (can be stored
efficiently in an array)
• Want to have a pointer based representation
of trees
• Each node stores
– an element
– has a pointer to the left subtree (might be empty)
– has a point to the right subtree (might be empty)
Data Structures and Algorithms
TreeItem
Class Handle = Pointer to TreeItem
Class TreeItem of Element
e: Element
right: Handle
left: Handle
Data Structures and Algorithms
e
right
left
Tree Traversal
• Want to visit every node in the tree (and print
out the elements).
• Recursive formulation for tree traversal
Data Structures and Algorithms
Preorder Traversal
Preorder(Tree T)
1. Visit the root (and print out the element)
2. If (T->left !=null) Preorder(T->left)
3. If (T->right !=null) Preorder(T->right)
Data Structures and Algorithms
Preorder Traversal
Data Structures and Algorithms
7
3 13
2 11
17
19
5
18 22
Order nodes are visited: 17, 7, 3, 2, 5, 13, 11, 19, 18, 22
Postorder Traversal
Postorder(Tree T)
1. If (T->left !=null) Postorder(T->left)
2. If (T->right !=null) Postorder(T->right)
3. Visit the root (and print out the element)
Data Structures and Algorithms
Postorder Traversal
Data Structures and Algorithms
7
3 13
2 11
17
19
5
18 22
Order nodes are visited: 2, 5, 3, 11, 13, 7, 18, 22, 19, 17
Inorder Traversal
Inorder(Tree T)
1. If (T->left !=null) Inorder(T->left)
2. Visit the root (and print out the element)
3. If (T->right !=null) Inorder(T->right)
Data Structures and Algorithms
Inorder Traversal
Data Structures and Algorithms
7
3 13
2 11
17
19
5
18 22
Order nodes are visited: 2, 3, 5, 7, 11, 13, 17, 18, 19, 22
Observation: This sequence is sorted
Sorted Sequences
Operations for Sorted Sequences
• Find an element e in the sorted sequence
• Insert an element e into the sorted sequence
• Delete an element e from the sorted
sequence.
Data Structures and Algorithms
Want to have all these operations implemented in time O(log n).
Binary Search Tree
Data Structures and Algorithms
7
3 13
2 11
17
Sorted sequence by Inorder Traversal: 2, 3, 5, 7, 11, 13, 17, 18, 19, 22
19
5
18 22
Properties of Binary Search Trees
• All elements in the left subtree of a node k
have value smaller than k.
• All elements in the right subtree of a node k
have value larger than k.
Data Structures and Algorithms
Method find
find(k)
• Start at the root.
• At a node x, compare x and k.
1. If k=x, then found
2. If k < x, search in the left subtree of x. If
subtree does not exist return not found.
3. If k > x, search in the right subtree of x. If
subtree does not exist, return not found
Data Structures and Algorithms
Find
Data Structures and Algorithms
7
3 13
2 11
17
19
5
Find 11
18 22
Find
Data Structures and Algorithms
7
3 13
2 11
17
19
5
Find 11
18 22
Insertion
insert(k)
1. find(k)
2. If not found, element with key k becomes
child of the last visited node of find(k).
Data Structures and Algorithms
Insert
Data Structures and Algorithms
7
3 13
2 11
17
19
5
Insert 14
18 22
Insert
Data Structures and Algorithms
7
3 13
2 11
17
19
5
Insert 14
14
Last visited node for find(14)
18 22
Remove
remove(k)
1. find(k)
• If k is stored at a leaf, delete this leaf and the
incoming edge.
• If k has one child x, redirect pointer pointing to k
to x and delete k.
• If k has two children
– search in the tree for the largest element x smaller
than k.
– swap x and k and delete(k)
Data Structures and Algorithms
Remove leaf
Data Structures and Algorithms
7
3 13
2 11
17
19
5
Remove 2
18 22
Remove leaf
Data Structures and Algorithms
7
3 13
11
17
19
5
Remove 2
18 22
Remove node with 1 child
Data Structures and Algorithms
7
3 13
11
17
19
5
Remove 3
18 22
Remove node with 1 child
Data Structures and Algorithms
7
5 13
11
17
19
3
Remove 3
18 22
Remove node with 1 child
Data Structures and Algorithms
7
5 13
11
17
19
Remove 3
18 22
Remove node with 2 children
How to find the largest element smaller than k?
• Go to the left child of k (has to exist as k has
two children.
• Follow the pointer to the right as long as
possible.
Data Structures and Algorithms
Remove node with 2 children
Data Structures and Algorithms
7
5 13
11
17
19
Remove 17
18 22
Swap 13 and 17
Remove node with 2 children
Data Structures and Algorithms
7
5 17
11
13
19
Remove 17
18 22
Remove node with 2 children
Data Structures and Algorithms
7
5 11
17
13
19
Remove 17
18 22
Remove node with 2 children
Data Structures and Algorithms
7
5 11
13
19
Remove 17
18 22
Perfectly Balanced Binary Search Trees
• A binary search tree is perfectly balanced if it
has height (height is the length of the
longest path from the root to a leaf)
Data Structures and Algorithms
Insertion
Data Structures and Algorithms
19 Insert 17
Insertion
Data Structures and Algorithms
19 Insert 13
17
Insertion
Data Structures and Algorithms
19 Insert 11
17
13
Insertion
Data Structures and Algorithms
19 Insert 7
17
13
11
Insertion
Data Structures and Algorithms
19
17
13
11
7
Problem?
Tree can degenerate to a list.
…