Learning Outcomes- Define trees, binary trees and binary search trees
- Perform inorder, preorder and postorder traversals
- Insert into and search a binary search tree
- Understand heaps and balanced trees
Trees and Binary Trees
A tree is a hierarchical collection of nodes with a single root, and a binary tree restricts each node to at most two children. Important terms include height, depth, leaf node and subtree.
struct TNode {
int data;
TNode* left;
TNode* right;
};
Binary Search Trees
A binary search tree keeps smaller keys on the left and larger keys on the right, giving average O(log n) search, insertion and deletion. An inorder traversal of a BST visits keys in sorted order.
TNode* insert(TNode* r, int x){
if (!r) return new TNode{x, 0, 0};
if (x < r->data) r->left = insert(r->left, x);
else r->right = insert(r->right, x);
return r;
}
Heaps and Balanced Trees
A binary heap is a complete tree that maintains the heap property and powers priority queues and heap sort, while AVL and Red-Black trees rebalance themselves to guarantee O(log n) height.
// inorder traversal
void inorder(TNode* r){
if (!r) return;
inorder(r->left);
cout << r->data << " ";
inorder(r->right);
}
Summary
This unit introduced tree terminology, binary search trees with their traversals and operations, and the heaps and self-balancing trees that guarantee efficient performance.
Exercises
- Write code to count the number of leaf nodes in a binary tree.
- Implement inorder, preorder and postorder traversal.
- Insert a sequence of keys into a BST and show the inorder output.
- Explain how a max-heap supports a priority queue.