Data Structures and Algorithms

Binary Search Trees Sundaresan Raman

T such that for each internal node v

subtree of v are greater than or 3

equal to k 7

5 8

5
Searching a Binary Search Tree
5

3 10

2 5 7 11

• To find an element with key k in a tree T:

Search(T,11)

3 10

2 5 7 11

4
Element 11
found!
Searching a Binary Search Tree

Search(T, 6)

3 10

2 5 7 11

4
Element 6
Not found!
Pseudocode for Search in a BST (Recursive)
Recursive version:
// Searches for key k in Tree T. Returns the key if found in T, Returns NIL otherwise.
Algorithm Search(T, k)
x ← T.root
if x = NIL then
return NIL
if k = x.key then
return x
if k < x.key then
return Search(x.left, k)
else
return Search(x.right, k)
Pseudocode for Search in a BST (Iterative)
Iterative version:
// Searches for key k in Tree T. Returns the key if found in T, Returns NIL otherwise.
Algorithm Search(T, k)
x ← T.root
while x ≠ NIL and k ≠ x.key do
if k < x.key then
x ← x.left
else
x ← x.right
return x
Time Complexity of Search in a BST
• Running time on tree of height h is O(h)
• After the insertion of n keys, the worst-case running time of searching is O(n)
• Occurs in the following case:

11

15
BST Minimum (Maximum)

3 10

2 5 7 11

Minimum Maximum
Element Element
BST Minimum (Maximum)
Find the minimum key in a tree rooted at x

Algorithm TreeMinimum(x)
while x.left ≠ NIL do
x ← x.left
return x
Running time: O(h)
Successor
• Given x, find the node with the smallest key greater than x.key.
• There are two cases to be considered to compute the successor of x.
• Case 1: Right subtree of x is non-empty.
• Successor of x is leftmost node in the right subtree of x.
• Can be computed as TreeMinimum(x.right).

5 x

1 10

1 3 7 11

8 Successor of x
Successor (contd.)
• Case 2: Right subtree of x is empty.
• Successor of x is the lowest ancestor of x whose left child is also an ancestor of x.

5 Successor of x

1 10
x

1 3 7 11

8
Successor: Pseudocode
Algorithm TreeSuccessor(x)
if x.right ≠ NIL then
return TreeMinimum(x.right)
y ← x.parent
while y ≠ NIL and x = y.right do
x←y
y ← y.parent
return y

Running time: O(h)

Follows a similar approach as that of

Self-Study!
BST Insertion
• Idea: Similar to searching
• To insert an element z into a BST T:
• Find place in T where z belongs (as if searching for z)
• Add z there
• Running time: O(h)
BST Insertion (contd.)
Insert 8

3 10

2 5 7 11

8
4
BST Insertion Pseudocode
Algorithm TreeInsert(T, z)
y ← NIL
x ← T.root
while x ≠ NIL do
y←x
if z.key < x.key then
x ← x.left
else
x ← x.right
z.parent ← y
if y = NIL then
T.root ← z
else if z.key < y.key then
y.left ← z
else
y.right ← z
BST Insertion Time Complexity
• Running time: O(h)
• Worst case: O(n)
• Occurs when the sequence of elements to be inserted into the BST are already
sorted

11

15
BST Deletion
• To delete a node z from a tree T, there are three possible cases:
• z has no children
• z has one child
• z has two children
BST Deletion (contd.)
Case 1: z has no children
• Just remove z

Example: Delete 4

5 5

3 10 3 10

z 4 7 7
BST Deletion (contd.)
Case 2: z has one child
• To delete z, make z.parent point to
that child
Example: Delete 3

5 5

z 3 10 10

4 7 4 7
BST Deletion (contd.)
Case 3: z has two children. To delete z:
• Find successor of z (say y)
• Remove y (y will have utmost one child)
• Replace z with y
Example: Delete 5

z 5 7

3 10 3 10

4 7 4

y
BST Deletion: Pseudocode
Algorithm TreeDelete(T, z) if x ≠ NIL then
if z.left = NIL or z.right = NIL then x.parent ← y.parent
y←z if y.parent = NIL then
else T.root ← x
y ← TreeSuccessor(z) else if y = y.parent.left then
if y.left ≠ NIL then y.parent.left ← x
x ← y.left else
else y.parent.right ← x
x ← y.right
if y ≠ z then
z.key ← y.key
return y
Running time: O(h)
In Order Traversal of a BST
• In order traversal of a BST can be thought of its projection onto a one-dimensional
interval.

3 10

2 5 7 11

2 3 5 5 7 10 11
BST Sorting
• Given n elements to be sorted.
• Insert all of them into a BST.
• Perform in-order traversal on the BST and store the nodes visited in the traversal in our array,
which would be sorted after all nodes are visited.

// Given an array A of n elements. This algorithm sorts these n elements using BST Sort.
Algorithm TreeSort(A)
T.root ← NIL
for i ← 1, i < n do
TreeInsert(T, A[i])
InOrderTreeWalk(T.root)
BST Sorting (Illustration)
• Example: Sort the following numbers: 5 10 7 1 3 1 8
• Build a binary search tree

5 5 5

10 10

7 5

1 10

• Call InorderTreeWalk: 3 7

1 1 3 5 7 8 10
1 8
Thank You!