11.

Trees

Dr. Swati Agarwal

Agenda
1 Binary Search Trees
Properties of a BST
Operations on BSTs
Structure of a BST

2 Finding an element in BSTs

Finding minimum element in BSTs
Finding maximum element in BSTs

3 Inserting an element in BSTs

4 Deleting an element from BSTs

March 17, 2020 Dr. Swati Agarwal 11. Trees 2/27

Binary Search Tree
1. Binary Search Trees (BSTs)

Applies the motivation of the binary search procedure to a

tree-based data structure

We define a binary tree to be BST where each internal node v

stores an element e such that
• the elements stored in the left subtree of v are lesser than or
equal to e
• the elements stored in right subtree of v are greater than or
equal to e.

Assume that external nodes store no elements and they in fact

be NULL or reference to NULL NODE object.

March 17, 2020 Dr. Swati Agarwal 11. Trees 4/27

BST: Example
7
5 10
2 6 8 15

A BST
4

1 16

2 3 18 25
Not a BST

March 17, 2020 Dr. Swati Agarwal 11. Trees 5/27

1.1 Properties of a BST

Am inorder traversal of a BST visits the elements in a

non-decreasing sorted order.
A BST supports searching, where the question asked at each
internal node is whether the element at the node is less than
or equal to OR greater than or equal to the element being
searched for.
As a result it reduces the worst case complexity to O(log n)
Since root data is always between left subtree data and right
subtree data, the InOrder Traversal on a BST always produces
a sorted list of elements.
While performing INSERTION or DELETION operations, we
must preserve the structure of BST.
March 17, 2020 Dr. Swati Agarwal 11. Trees 6/27
1.2 Operations on BSTs

ADT Operations
• find/find minimum/find maximum element in BST
• inserting an element in BST
• deleting an element from BST

Auxiliary Operations
• finding k th smallest element in BST
• sorting the elements of a BST

March 17, 2020 Dr. Swati Agarwal 11. Trees 7/27

1.3 Structure of a BST
Based on the input sequence, a variety of BSTs can be
created for the same set of elements. For example, the first
two trees below look reasonably well ”balanced”.
4 3 1
2 5 2 5 2
1 3 6 1 4 6 3
4
5
6
However, this is not always the case. For instance, the third
example is a highly unbalanced search tree over the same set
of values.
March 17, 2020 Dr. Swati Agarwal 11. Trees 8/27
Searching an Element
2. Searching an Element in BST

Recursive Algorithm Non-Recursive Algorithm

function Find(∗root, x) function Find(∗root, x)
if root == x then while root
return root if root == x then
else if root > x then return root
Find(left[root], x) else if root > x then
else root ← left[root]
Find(right[root], x) else
root ← right[root]
return −1
return −1

Time Complexity of the algorithm: O(h), where h represents the

height of the tree. O(log n) in average case while O(n) in the
worst case (skew tree).

March 17, 2020 Dr. Swati Agarwal 11. Trees 10/27

2.1 Finding Minimum Value Element in BSTs

In a BST, the minimum value element is the left-most node

which doesn’t have a left child. For example, in the below
tree, the minimum element is 1.
20
14 30
7 18 23 35
4 9 21 27
1 5

March 17, 2020 Dr. Swati Agarwal 11. Trees 11/27

2.1 Finding Minimum Value Element in BSTs
function FindMinimum(∗root)
if root == NULL then
return NULL
else if root −→ left == NULL then
return root
else
return FindMinimum(root −→ left)

Time Complexity: O(n) in worst case if the tree is a left skew

tree.

March 17, 2020 Dr. Swati Agarwal 11. Trees 12/27

2.2 Finding Maximum Value Element in BSTs

In a BST, the maximum value element is the right-most node

which doesn’t have a right child. For example, in the tree
(Slide 11), the maximum element is 35.
function FindMaximum(∗root)
if root == NULL then
return NULL
else if root −→ right == NULL then
return root
else
return FindMaximum(root −→ right)

Time Complexity: O(n) in worst case if the tree is a right skew

tree.
March 17, 2020 Dr. Swati Agarwal 11. Trees 13/27
Inserting an element
3. Inserting an element in BSTs

To insert an element in BST, first we need to find the location

for the element. (FIND algorithm).
If the element is already there in the tree, we can return
Otherwise, insert data at the last location on the path
traversed.
function Insert BST(∗root, x)
if root == NULL then
data[root] = x
left[root] = right[root] = 0
else if data[root] < x then
Insert BST(right[root], x)
else
Insert BST(left[root], x)

March 17, 2020 Dr. Swati Agarwal 11. Trees 15/27

Example: Inserting an Element
Input: 13, 16, 31, 7, 19, 10, 8, 4

13 13 13 13 13
16 16 7 16 7 16
31 31 31
19

13 13 13
7 16 7 16 7 16
10 31 10 31 4 10 31
19 8 19 8 19

March 17, 2020 Dr. Swati Agarwal 11. Trees 16/27

Deleting an element
4. Deleting an Element from BSTs

Given the below example of generic BST, suppose we want to

delete a value x from a tree whose root is y .
• If x < y , we inductively delete x from the left subtree of y .
• Similarly, if y < x, we inductively delete x from the right
subtree of y .

The problem of deletion operation becomes interesting when

x == y .

w z
t1 t2 t3 t4

March 17, 2020 Dr. Swati Agarwal 11. Trees 18/27

4. Deleting an Element from BSTs
Once we have found the element to be deleted, there can be
following cases:

1. Element is a leaf node

2. Element is an intermediate node and

• has one child (sub-tree)
• has two children (sub-trees)

March 17, 2020 Dr. Swati Agarwal 11. Trees 19/27

4.1 Deleting a Leaf Node
Delete the node and return NULL to it’s parent (make the
corresponding child pointer NULL).
13 13
7 16 7 16
4 10 31 4 10 31
8 19 50 8 19 NULL

March 17, 2020 Dr. Swati Agarwal 11. Trees 20/27

4.2 Deleting a Node with One Child/Sub-Tree

Delete the node and create a link between its parent node and
child node.
That means replace the node to be deleted with it’s child.

13 13
7 16 7 31
4 10 31 4 10 19
8 19 8

March 17, 2020 Dr. Swati Agarwal 11. Trees 21/27

4.3 Delete a Node with Both Sub-Trees
If we remove y , there is an ”empty” node at the root of the tree.

A basic idea that might come to your mind is to move either

w or z into this place and recursively delete w from the left
subtree (or z from right subtree).

However this will not work, since the value t2 greater than w
will end up to the left of w . Similarly, the value t3 which is
smaller than z will end up in the right of the z.
y w z
w z t2 z w t3
t1 t2 t3 t4 t1 t3 t4 t1 t2 t4

March 17, 2020 Dr. Swati Agarwal 11. Trees 22/27

4.3 Delete a Node with Both Sub-Trees

The general and correct solution will be to delete the node

and move it’s InOrder predecessor or InOrder successor in
place of y and recursively delete that node.

InOrder Predecessor: the largest element from the left subtree.

InOrder Successor: the smallest element from the right

subtree.

The largest element from the left sub-tree can be found by

applying FIND MAXIMUM() algorithm.

The smallest element from the right subtree can be found by

applying FIND MINIMUM() algorithm.

March 17, 2020 Dr. Swati Agarwal 11. Trees 23/27

4.3 Delete a Node with Both Sub-Trees
function Delete(∗root, x)
if root > x then
left[root] = Delete(left[root], x)
else if root < x then
right[root] = Delete(right[root], x)
else . found element: has both sub-trees
if left[root]&&right[root] then
temp= FindMaximum(left[root]) . predecessor method
data[root] = data[temp]
left[root] = Delete(left[root], data[root])
else . found element: has one sub-tree
temp = root
if left[root] = NULL then
root = right[root]
else
root = left[root]
return root
March 17, 2020 Dr. Swati Agarwal 11. Trees 24/27
4.3.1 InOrder Predecessor Method
10
7 16
13
4 X 31
7 16
8 19 50
move 10 in place of 13. Now perform dele-
4 10 31
tion operation on 10
8 19 50 10
InOrder Traversal:
4, 7, 8, 10, 13, 16, 19, 31, 50 7 16
Predecessor: 10
4 8 31
19 50

March 17, 2020 Dr. Swati Agarwal 11. Trees 25/27

4.3.1 InOrder Successor Method
16
7 X
13 4 10 31
7 16 8 19 50
4 10 31 move 16 in place of 13. Now perform dele-
tion operation on 16
8 19 50 16
InOrder Traversal:
4, 7, 8, 10, 13, 16, 19, 31, 50 7 19
Successor: 16
4 10 31
8 NULL 50

March 17, 2020 Dr. Swati Agarwal 11. Trees 26/27

Applications of a BST

Binary Search
Dictionary Search
Efficient storage of Term Vocabulary in Search Engine design
Multi-level indexing in databases.
Wildcard queries in Search Engine

March 17, 2020 Dr. Swati Agarwal 11. Trees 27/27