Binary Search Tree (BST) Explained Step-by-Step

A Binary Search Tree (BST) is a specialized data structure that organizes data hierarchically, allowing efficient data retrieval, insertion, and deletion operations. Each node in a BST contains a key, and it has two subtrees: a left subtree and a right subtree. The unique characteristic of a BST is its ordering property, which dictates that for any given node, all nodes in its left subtree contain keys less than the node's key, and all nodes in its right subtree contain keys greater than the node's key. This structured approach facilitates quick searching, as it enables a divide-and-conquer method by allowing half of the nodes to be disregarded with each comparison, similar to a binary search process. BSTs are commonly employed in applications that require dynamic data sets, such as dictionaries, databases, and file systems, due to their balanced performance across operations. The efficiency of BST operations is determined by the tree’s height; ideally, in a balanced BST, each level of the tree is as fully populated as possible, yielding a height of O(log n), where n is the number of nodes. This optimal height provides efficient search, insertion, and deletion operations in O(log n) time. However, in cases where the BST becomes unbalanced—such as when nodes are inserted in an ascending or descending order—the tree degrades to a linear structure with a height of O(n), leading to inefficient O(n) performance for the operations. To counteract this, balanced BST variants, like AVL trees and Red-Black trees, automatically restructure the tree to maintain logarithmic height, preserving efficiency. When implementing a BST, common operations include searching for a value by comparing keys from the root node downwards, inserting a new node by traversing to the appropriate leaf position, and deleting a node, which requires additional consideration for restructuring the tree. For instance, when removing a node with two children, the in-order successor (or predecessor) of the node is typically found and promoted to preserve the BST’s order. This organized and adaptable nature makes BSTs integral in computer science for managing ordered data in a flexible, efficient manner, suited to dynamic applications that benefit from frequent updates. BSTs also support in-order traversal, which visits nodes in ascending order of keys, enabling sorted output of stored values, and they allow pre-order and post-order traversals for specific data-processing tasks.

1. Data Structure and Algorithms
Binary Search Tree
Advanced DS
University of Engineering and Technology
Lahore Pakistan
eduko.spikotech.com
Fall2024

2. Binary Search Tree
Course Reference: CS161 by Stanford
Data Structures and Algorithms

3. Some data structures
for storing objects like (aka, nodeswith keys)
•(Sorted) arrays:
•Linked lists:
•Some basic operations:
•INSERT, DELETE, SEARCH
82 473 1 5
HEAD
42 871 3 5
5
Data Structures and Algorithms

4. Sorted Arrays
•O(n) INSERT/DELETE:
•First, find the relevant element (we’ll see how below), and
then move a bunch elements in the array:
•O(log(n)) SEARCH:
42 871 3 5
421 3
42 871 3 5
eg, Binary search to see if 3 is in A.
8754.5
eg, insert 4.5
Data Structures and Algorithms

5. (Not necessarily sorted)
Linkedlists
•O(1) INSERT:
•O(n) SEARCH/DELETE:
45 827 3 1
45 827 3 1
HEAD
6
45 827 3 1
HEAD
eg, insert 6
eg, search for 1 (and then you could delete it by manipulating pointers).
Data Structures and Algorithms

6. Motivation for Binary Search Trees
SortedArraysLinked Lists
Binary Search
Trees
Search O(log(n)) O(n) O(log(n))
Delete O(n) O(n) O(log(n))
Insert O(n) O(1) O(log(n))
(Balanced)
Data Structures and Algorithms

7. Binary tree terminology
42 8
7
1
3
5
This node is
the root
This is a node .
It has a key(7).
These nodes
are leaves.
The leftchild of is32
The right child of is34
Both children of are NIL.
(I won’t usually draw them).
1
For today all keys are distinct.
Each node has two children.
NILNIL
Each node has a pointer to its left child, right child, and parent.
The parent of is
35
is a descendantof 2 5
The height of this tree is 3.
(Max number of edges from the
root to a leaf).
Data Structures and Algorithms

8. Binary Search Trees
4
2
8 7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
•Example of building a binary search tree:
From your pre-lecture exercise…
Data Structures and Algorithms

9. Binary Search Trees
4
2
8 7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
•Example of building a binary search tree:
Data Structures and Algorithms

10. Binary Search Trees
4
2
8
7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
•Example of building a binary search tree:
Data Structures and Algorithms

11. Binary Search Trees
4
2
8
7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
•Example of building a binary search tree:
Data Structures and Algorithms

12. Binary Search Trees
42 8
7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
•Example of building a binary search tree:
Q: Is this the only
binary search tree I
could possibly build
with these values?
A: No.I made
choices about
which nodes to
choose when. Any
choices would
have been fine.
Data Structures and Algorithms

13. Aside: this should look familiar
4
2
8 7
1
3
5
kindalike QuickSort
Data Structures and Algorithms

14. Binary Search Trees
42 8
7
1
3
5
•A BST is a binary tree so that:
•Every LEFT descendant of a node has key less than that node.
•Every RIGHT descendant of a node has key larger than that node.
42 8
7
1
3
5
Binary Search Tree
NOTa Binary
Search Tree
Which of these is a BST?
1 minute Think-Pair-Share
Data Structures and Algorithms

15. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
Data Structures and Algorithms

16. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
Data Structures and Algorithms

17. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
NILNIL
Data Structures and Algorithms

18. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
NILNIL
Data Structures and Algorithms

19. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
2
NILNIL
Data Structures and Algorithms

20. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
2
NILNIL
Data Structures and Algorithms

21. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
2
NILNIL
Data Structures and Algorithms

22. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
23
Data Structures and Algorithms

23. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
234
Data Structures and Algorithms

24. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
234
Data Structures and Algorithms

25. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
2345
Data Structures and Algorithms

26. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
23457
Data Structures and Algorithms

27. Aside: In-Order Traversal of BSTs
•Output all the elements in sorted order!
•inOrderTraversal(x):
•if x!= NIL:
•inOrderTraversal( x.left)
•print( x.key)
•inOrderTraversal( x.right)
42
73
5
23457 Sorted!•Runs in time O(n).
Data Structures and Algorithms

28. Tree Minimum and Tree Maximum
Data Structures and Algorithms
42 8
7
1
3
5

29. Tree Successor
Data Structures and Algorithms
42 8
7
1
3
5

30. Tree Predecessor
Data Structures and Algorithms
42 8
7
1
3
5

31. Back to the goal
Fast SEARCH/ INSERT/DELETE
Can we do these?
Data Structures and Algorithms

32. SEARCH in a Binary Search Tree
definition by example
42 8
7
1
3
5
EXAMPLE: Search for 4.
EXAMPLE: Search for 4.5
•It turns out it will be convenient
to return 4 in this case
•(that is, returnthe last node
before we went off the tree)
Ollie the over-achieving ostrich
Write pseudocode
(or actual code) to
implement this!
How long does this take?
O(length of longest path) = O(height)
Data Structures and Algorithms

33. INSERT in a Binary Search Tree
42 8
7
1
3
5
EXAMPLE: Insert 4.5
4.5
•INSERT(key):
•x = SEARCH(key)
•Insert a new node with
desired key at x…
x = 4
Data Structures and Algorithms

34. INSERT in a Binary Search Tree
42 8
7
1
3
5
EXAMPLE: Insert 4.5
4.5
•INSERT(key):
•x = SEARCH(key)
•if key > x.key:
•Make a new node with the
correct key, and put it as the
right child of x.
•if key < x.key:
•Make a new node with the
correct key, and put it as the
left child of x.
•ifx.key== key:
•return
x = 4
Data Structures and Algorithms

35. DELETE in a Binary Search Tree
42 8
7
1
3
5
EXAMPLE: Delete 2
•DELETE(key):
•x = SEARCH(key)
•ifx.key== key:
•….delete x….
x = 2
Data Structures and Algorithms

36. DELETE in a Binary Search Tree
several cases (by example)
say we want to delete 3
This triangle
is a cartoon
for a subtree
3
Case 1: if 3 is a leaf,
just delete it.
2
3
Case 2: if 3 has just one child,
move that up.
5 5
2
55
Siggithe Studious Stork
Write pseudocode for all of these!
Data Structures and Algorithms

37. DELETE in a Binary Search Tree
ctd.
42
3
5
3.1
2
5
Case 3: if 3 has two children,
replace 3 with it’s immediate successor.
(aka, next biggest thing after 3)
•Does this maintain the BST
property?
•Yes.
•How do we find the
immediate successor?
•SEARCH for 3 in the subtree
under 3.right
•How do we remove it when
we find it?
•If [3.1] has 0 or 1 children,
do one of the previous cases.
•What if [3.1] has two
children?
•It doesn’t.
4
3.1
Data Structures and Algorithms

38. How long do these operations take?
•SEARCHis the big one.
•Everything else just calls SEARCHand then does some
small O(1)-time operation.
42 8
73
5
6
Time = O(height of tree)
Trees have depth
O(log(n)). Done!
Lucky the
lackadaisical lemur.
How long does search take?
1 minute think; 1 minute pair+share
Wait a
second…
Plucky the
Pedantic Penguin
Data Structures and Algorithms

39. Search might take time O(n).
4
2
8
7
3
5
6
•This is a valid binary search tree.
•The version with n nodes has
depth n, notO(log(n)).
Data Structures and Algorithms

40. What to do?
•Goal: Fast SEARCH/INSERT/DELETE
•All these things take time O(height)
•And the height might be big!!! 
•Idea 0:
•Keep track of how deep the tree is getting.
•If it gets too tall, re-do everything from scratch.
•At least Ω(n) every so often… .
Ollie the over-achieving ostrich
How often is “every so
often” in the worst case?
It’s actually pretty often!
Data Structures and Algorithms