#### Overview of this book

Choosing the right data structure is pivotal to optimizing the performance and scalability of applications. This new edition of Hands-On Data Structures and Algorithms with Python will expand your understanding of key structures, including stacks, queues, and lists, and also show you how to apply priority queues and heaps in applications. You’ll learn how to analyze and compare Python algorithms, and understand which algorithms should be used for a problem based on running time and computational complexity. You will also become confident organizing your code in a manageable, consistent, and scalable way, which will boost your productivity as a Python developer. By the end of this Python book, you’ll be able to manipulate the most important data structures and algorithms to more efficiently store, organize, and access data in your applications.
Preface
Free Chapter
Python Data Types and Structures
Introduction to Algorithm Design
Algorithm Design Techniques and Strategies
Stacks and Queues
Trees
Heaps and Priority Queues
Hash Tables
Graphs and Algorithms
Searching
Sorting
Selection Algorithms
String Matching Algorithms
Other Books You May Enjoy
Index

# Binary search trees

A binary search tree (BST) is a special kind of binary tree. It is one of the most important and commonly used data structures in computer science applications. A binary search tree is a tree that is structurally a binary tree, and stores data in its nodes very efficiently. It provides very fast search, insertion, and deletion operations.

A binary tree is called a binary search tree if the value at any node in the tree is greater than the values in all the nodes of its left subtree, and less than (or equal to) the values of all the nodes of the right subtree. For example, if `K1`, `K2`, and `K3` are key values in a tree of three nodes (as shown in Figure 6.22), then it should satisfy the following conditions:

• The key values K2<=K1
• The key values K3>K1

The following figure depicts the above condition of the binary search tree:

Figure 6.22: An example of a binary search tree

Let’s consider another example so that...