Trees (preview)
Nodes with two children, and the three traversal orders
In a nutshell
A binary tree is a linked structure where each node points to up to two children: left and right. A binary search tree (BST) imposes an ordering invariant: for every node, everything in the left subtree is smaller and everything in the right subtree is larger. Search, insert, and delete become O(log n) if the tree stays balanced. The three traversal orders (pre-order, in-order, post-order) differ only in whether you process the node before, between, or after the recursive calls on its children.
Why it matters
Every filesystem is a tree. Every HTML document is a tree. Expression evaluation, game-AI decisions, compression codes, database indices — all trees. You will not write a red-black tree in this class, but you will write a small BST, and you will walk trees recursively. The practice here makes CSCD 360 (Operating Systems), CSCD 330 (Networks), and later data structures classes easier.
Key takeaways
- Node definition.
typedef struct TreeNode { int value; struct TreeNode *left; struct TreeNode *right; } TreeNode;. - BST invariant. Every insert, delete, and search uses the left-smaller / right-larger rule to halve the search space.
- Pre-order, in-order, post-order differ only in when you process the node relative to the recursive calls on its children.
- In-order of a BST yields the values in sorted order.
- Balance matters. A pathological input can turn a BST into a linked list (O(n) operations). Self-balancing trees (AVL, red-black) fix this; they are a later class.
Lessons in this topic
(Lesson pages for week 8 are being authored.)
Practice and deep dives
Practice this topic: browse the practice gallery.
What comes next
Week 9 shifts to systems programming. Processes introduces fork and exec: how a shell spawns a program, how a web server handles multiple connections, how any multi-process Unix system is built.