Summary - BST
- Algorithms course
- Intermediate
- Lesson 32/80
- 4 min
Insert items into a BST and print them in-order in a mini task.
Summary - BST
BST: left smaller, node, right larger. Search, insert, delete are O(log n) on a balanced BST; O(n) when unbalanced.
Inorder traversal gives increasing order. Duplicates are usually rejected. AVL or red-black trees provide automatic balance.
The BST is a fundamental data structure for fast search, insert and delete on sorted data.
Practice Summary: BST inorder
Write inorder(node). Left-root-right; collect values into a list. Print [2, 4, 6] with root = Node(4); root.left = Node(2); root.right = Node(6); print(inorder(root)).
Starter code
def inorder(node):
# Left-root-right, return listSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorder(node):
# Left-root-right, return list
if node is None:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = Node(4)
root.left = Node(2)
root.right = Node(6)
print(inorder(root))Expected output
[2, 4, 6]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - BST: match the terms
| Term | Meaning |
|---|---|
Search |
O(log n) |
Unbalanced |
O(n) |
Inorder |
Increasing |
Duplicate |
Reject |
2 Inorder result
Question
BST inorder traversal = ____ order
Answer
BST inorder traversal = artan orderExplanation: artan is right.
3 What is the BST's biggest advantage?
- Fast search+insert+delete Correct answer
- Simple code
- Stable sort
- Less memory
Explanation: Fast search+insert+delete