Data Structures · topic
Binary tree terminology and the node, leaf and height relations, full, complete and perfect trees, k-ary trees, array representation, traversals and reconstruction from two traversals, expression trees, Catalan counts of shapes and labelled trees, and threaded trees.
Binary tree terminology with the height convention made explicit, the node, leaf, edge and NULL-link relations, maximum and minimum nodes for a height, full, complete and perfect trees with their counts, full k-ary trees, and the array representation with its worst-case waste. Every relation is checked by brute force over all tree shapes with up to 9 nodes.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
Preorder, inorder, postorder and level-order traversal with their time and space costs, iterative inorder with a stack, rebuilding a binary tree from preorder or postorder plus inorder with two worked traces, which traversal pairs fix a unique tree and how many trees share an ambiguous pair, positional facts about first and last nodes, and threaded binary trees. Uniqueness claims are checked by brute force.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
Expression trees and how preorder, inorder and postorder give prefix, infix and postfix, building one from a postfix string, Catalan counts of binary tree shapes, labelled trees and binary search trees (also with a fixed root), chains and full trees, the left-child right-sibling form of general trees, and recursive tree functions in compiled C. Counts are brute-forced over all shapes and permutations.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
