Quick Index
What is a Binary Search Tree (BST)?

Basics


A BST is a structure that provides:


NOTE WELL -- for the following diagrams assume every node has data (an element), and every element has a key. We may abbreviate this as something like "current node's key" or just "key". And in diagrams, we may just show keys to simplify.

Example 1 - BST of Customers sorted by ID
A BST looks like this. Each node has data and has a left and right sub-node.

In this particular tree, the key is the customer id (e.g., id=20, id=10, etc). The key dictates where data is placed.

Keys that sort before the current node's key are placed left, and keys that sort equal or after the current node's key to the right.
                      Customer1
                       (id=20)
                         |
           --------------+--------------
           |                           |
       Customer6                   Customer3
        (id=10)                     (id=40)
           |                           |
    -------+-------             -----+
    |             |             |
Customer5      Customer2    Customer4
 (id=5)        (id=15)       (id=30)
Example 1 - Focus on Sort
Let's focus on Customer6 (key=10).

Data with keys that sort before this key (like 5) are placed left

Data with keys that sort equal or after this key (like 15) are placed right.
                      Customer1
                       (id=20)
                         |
           --------------+--------------
           |                           |
       Customer6                   Customer3
        (id=10)                     (id=40)
           |                           |
    -------+-------             -----+
    |             |             |
Customer5      Customer2    Customer4
 (id=5)        (id=15)       (id=30)
Example 1 - Abbreviated
Note that tree diagrams may be simplified to just show keys.

Here we show the Example 1 BST with just the keys.
              20
              |
     ---------+---------
     |                 |
     10                40
     |                 |
-----+-----       -----+
|         |       |
5         15      30
Example 2 - BST of Customers sorted by Name
This BST uses "name" as the sort key (which produces a different sort order).

The concepts are the same as Example 1.
                         Customer1
                       (name="Kofi")
                            |
              --------------+--------------
              |                           |
          Customer3                   Customer6
        (name="Chin")                (name="Riya")
              |                           |
       -------+-------               -----+
       |             |               |
  Customer2      Customer4       Customer5
(name="Asha")   (name="Fon")   (name="Mzia")
Example 2 - Focus on Sort
Let's consider the node with Customer3 (key="Chin").

Data with keys that sort before this key (like "Asha") are placed left

Data with keys that sort equal or after this key (like "Fon") are placed right.
                         Customer1
                       (name="Kofi")
                            |
              --------------+--------------
              |                           |
          Customer3                   Customer6
        (name="Chin")                (name="Riya")
              |                           |
       -------+-------               -----+
       |             |               |
  Customer2      Customer4       Customer5
(name="Asha")   (name="Fon")   (name="Mzia")
Linear Search Review
We know that a linear search is not efficient. The maximum search path includes all the elements.
BST - A Fast Searcher
Let's compare the same search using a BST. The maximum search path (e.g., 1-2-3-4 as shown) is only four nodes.

For a tree with 1,000,000 elements, the maximum search path is just 20 nodes. The reason for the tremendous gain in efficiency is that the BST effectively performs a binary search and thus takes logarithmic time (e.g. 1,000,000 reduces to 20).
                 
1
40
                  |
          --------+---------
          30               
2
60
          |                |
     -----+----       -----+-----
     10       35      50        
3
70
     |        |       |         |
   --+--    --+--   --+--     --+--
   4   12  33  37   48  53   
4
63   99
A Good Traverser
A BST also has traversal skills. It can be traversed in a variety of ways like the sorted traversal shown. Can you guess how it traverses? We'll learn how soon.

If we need fast searching, and the ability to traverse data (or search for a range), a BST is a good choice.
             11
             |
     --------+--------
     |               |
     8              43
     |               |
-----+-----     -----+-----
|         |     |         |
1         7    44        45


Basic Terms


The following is a listing of some important binary search tree terms.

The examples in this chapter will be a deeper dive into the terms.

Binary Tree
A tree where each tree node has two sub-nodes (of the same node type). One or both of the sub-nodes may be null. Each node is itself a tree (sub-tree).
Binary Search Tree (BST)
A BST is a ordered (sorted) binary tree. Each binary node has a left node (sub-tree) with smaller values, and right node (sub-tree) with equal or larger values.
BST Less/Equal/Greater
When talking about how a BST sorts and we say a value "A" is less than a value "B", this means that "A" sorts before "B".
BST Node
A BST is comprised of BST nodes. Each BST node has a left BST node and right BST node.
Sort Order
The sort order is: left sub-tree, target node, right sub-tree.
Sub-Tree
Any node in the tree is a sub-tree.






























Data Structures And Algorithms (DSA) (Chapter 702 - Binary Search Tree (BST) Concepts)










Chapter 702 - Binary Search Tree (BST) Concepts < Prev Intro Next >

Index Video Intro Tree Node Operations Traversal Balance Iterators Design Pros Refs

Chapter Top Search Site Contents