Python Programming: A modular approach

CHAPTER 15

DATA STRUCTURES III: BINARY SEARCH TRESS

CHAPTER OUTLINE

15.1 Definitions and Notations

15.2 Binary Search Tree

15.3 Traversal of Binary Search Trees

15.4 Building Binary Search Tree

In the previous chapters, we discussed linear data structures stacks, queues, and linked lists. However, there are situations that necessitate the use of the non-linear arrangement of data; for example, a directory is a hierarchical structure like a tree. In this chapter, we will briefly talk about trees and move on to study in detail binary search trees—a particular form of trees, used for efficiency in searching.

15.1 DEFINITIONS AND NOTATIONS

A tree is a hierarchical structure. It is a collection of elements called nodes along with a relation called ...