Scribd
Upload
7 views7 pages

DS Lab7

The document provides an overview of binary search trees (BST), detailing their properties, applications, and operations such as searching, insertion, and deletion. It includes a problem set with tasks to implement recursive functions for counting odd values, finding values greater than a given integer, and printing values within a specified range in a BST. The content is part of a lab exercise for a course on Data Structure and Algorithm Design at The British University in Egypt.

Uploaded by

mosalah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views7 pages

DS Lab7

The document provides an overview of binary search trees (BST), detailing their properties, applications, and operations such as searching, insertion, and deletion. It includes a problem set with tasks to implement recursive functions for counting odd values, finding values greater than a given integer, and printing values within a specified range in a BST. The content is part of a lab exercise for a course on Data Structure and Algorithm Design at The British University in Egypt.

Uploaded by

mosalah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

THE BRITISH UNIVERSITY IN EGYPT

18CSCI01C
Semester 2

Introduction to Data Structure and


Algorithm Design

LAB 7

1
Binary Search Trees:

A binary search tree, also known as an ordered binary tree, is an efficient variant of binary trees
in which the nodes are arranged in an order.

A binary search tree is a binary tree with the following properties:


 The left sub-tree of a node N contains values that are less than N’s value.
 The right sub-tree of a node N contains values that are greater than N’s value.
 Both the left and the right binary trees also satisfy these properties and, thus, are binary
search trees.

(Note that a binary search tree may or may not contain duplicate values, depending on its
implementation.)

Since the nodes in a binary search tree are ordered, the time needed to search an element in the
tree is greatly reduced. Whenever we search for an element, we do not need to traverse the entire
tree. At every node, we get a hint regarding which sub-tree to search in.

Binary Search Trees Applications:

1. Dynamic sorting and searching (efficiently maintain a dynamically changing dataset in


sorted order)
2. Dictionary problems (where the code always inserts and searches the elements that are
indexed by some key value.)
3. Multilevel indexing in Databases, such as CouchDB

Operations in BST:
By leveraging the left and right recursive definition of BST we can do:
 Searching
 Insertion
 Deletion
 Traversal: in-order, pre-order, post-order.
 Determining height of tree
 Counting Nodes of a tree

2
Problem Set:

Q1.
Write a recursive function CountOdd that counts the number of odd values stored in the
nodes in a BST tree.
The function should take as an input a pointer to the tree and return an integer number that
represents the total number of the odd values stored in the nodes in the BST.

Q2.
Write a recursive function GreaterThan that takes as input an integer value x and a pointer to the
root of the tree.
The function outputs, in ascending order all values in the BST that are greater than x. Note that
the value of x need not be stored in the tree.

Q3.
Write a recursive function PrintInRange that takes an input two integer values, and only prints
the values between the inputs.

3
Code:

4
5
6
Appendix.

You might also like