Trees

Binary trees, binary search trees, traversals, balanced trees and heaps.

1. 4.1Binary Trees & Tree TermsRoot, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.easy
2. 4.2Tree TraversalsPreorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.medium
3. 4.3Binary Search TreeLeft is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).medium
4. 4.4BST Delete (3 Cases)Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.hard
5. 4.5Heap SortBuild a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.hard
6. 4.6General Trees (Left-Child, Right-Sibling)Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.medium