The Self-Taught Computer Scientist

Figure 14.5: An example of a binary search tree

---

Data Structures
150
If you start from the root node and move only to right child nodes, you will walk through the nodes 
A, C, and E. If you instead move only to left child nodes, you will walk through the nodes A and B. 
You may have noticed that neither of these traversals includes the node D. To get to the node D, you 
must first move to the A node’s right child and then the C node’s left child. In other words, to get to 
the D node in this binary tree, you have to backtrack.
When to Use Trees
Inserting, deleting, and searching for data in a general and binary tree are all O(
n). Binary search trees 
are more efficient: all three operations in a binary search tree are logarithmic because you can do a 
binary search to insert, delete, and search for nodes in a binary search tree (Figure 14.7).
You may be wondering why, if every operation is linear, you should ever use a general or binary 
tree. Even binary search trees that allow you to search for data logarithmically are slower than hash 
tables, so why should you ever use trees? Trees enable you to store hierarchical information that would 
Root Node
Branch Node
Leaf Nodes
A
B
C
D
E
Figure 14.6: A simple tree showing the root node, A, and its descendants
Data 
Structure
Time Complexity
Average
Worst
Access
Search
Insertion Deletion
Access
Search
Insertion Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Linked 
List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Hash 
Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
Binary 
Search 
Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
O(n)
O(n)
O(n)