Binary Trees

By the end, you can

• Explain why each node has at most two children and how left and right sides differ.
• Define root, leaf, edge, depth, height, and subtree, and distinguish depth from height for the same node.
• Calculate the maximum nodes at a given level and the total nodes in a perfect tree of height h.
• Classify a binary tree as full, complete, or perfect given its structure.
• State the BST ordering invariant and trace a search through a BST step by step.
• Describe how insert and delete work on a BST, including the in-order successor replacement.
• Explain why O(h) cost is O(log n) in a balanced tree and O(n) in a degenerate one.
• Identify the sorted-insert pitfall and name the self-balancing trees that prevent it.