Trees
Hierarchical node structures built on the same pointer discipline as linked lists, traversed via recursion or an explicit stack/queue.
What it is
A tree is a connected, acyclic graph with a designated root, where each node has zero or more children. A binary tree restricts that to at most two children per node (left, right).
Traversal orders
- DFS: preorder (node, left, right), inorder (left, node, right — gives sorted order for a BST), postorder (left, right, node) — all naturally recursive, or iterative with an explicit stack.
- BFS: level order — process nodes level by level using a queue, useful whenever "level" or "depth" matters directly.
Binary Search Trees
A BST keeps every left subtree's values less than the node and every right subtree's values greater, giving O(log n) search/insert/delete if balanced — an unbalanced BST (e.g. inserting sorted data) degrades to a linked list, O(n).
Complexity
Traversal is always O(n) (every node visited once). Search/insert/delete depend entirely on tree shape: O(log n) balanced, O(n) worst case (a "tree" that's really a chain).
Why linked lists and stacks come first
Tree nodes are linked-list nodes with two pointers instead of one, and recursive traversal is exactly the call-stack pattern from the Stacks topic made explicit.