SME
Data Structures & Algorithms · Problem type
Preorder traversal of a search tree
Use this for “Insert 50, 30, 70, 20, 40, 60, 80 into an empty binary search tree. In what order does a preorder traversal visit the nodes?”
Put in order
Put the nodes in the order a preorder traversal visits them.
1
?
2
?
3
?
4
?
5
?
6
?
7
?
Assumptions
•
In a binary search tree, smaller keys go to the left subtree and larger keys to the right.
•
Preorder: the node, then its left subtree, then its right.
•
Each node is visited once, so the whole traversal takes time in proportion to the number of nodes.
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Trees and graphs
Main lesson
Heap array indices
Use this for “A heap is stored in an array from index 0. What are the parent and children of the node at index 5?”
Adjacency matrix or list size
Use this for “An undirected graph has 1000 vertices and 5000 edges. How many cells does its adjacency matrix take, and how many entries its adjacency list?”