Unit 16: Trees, Binary Search Trees, and Balancing
Branching structure instead of a straight line, the three orders you can walk a tree, and why an unbalanced tree quietly turns into a list.
7 topics · 25 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Tree Terminology: Root, Leaf, Height, and Depth
- How it worksHow do a tree's root, leaves, height, and depth each describe a different fact about its shape?
- Worked exampleFind the height and the number of leaves of a tree whose root has two children, one with two children of its own.
- Common mistakeWhy isn't a node's depth the same number as the tree's overall height?
Your turn1 of 2
A tree's root has 8 children, and one of those children has 7 children of its own, all of which are leaves. If the root's other children are also leaves, how many total leaves does the tree have?Binary Tree Traversals: Preorder, Inorder, and Postorder
- How it worksHow does preorder visit a node before its children while postorder visits a node only after both children?
- Worked exampleTrace the preorder, inorder, and postorder sequences for a tree with root 5, left child 3, and right child 8.
- Common mistakeWhy doesn't inorder traversal produce sorted output for just any binary tree?
Your turn1 of 2
A tree has 70 nodes total. Preorder, inorder, and postorder traversals each visit every node exactly once. How many total node visits occur across all three traversals combined?Level-Order Traversal: Breadth-First on a Tree
- How it worksHow does a queue-based level-order traversal visit every node at one depth before moving to the next depth?
- Worked exampleTrace a level-order traversal on a tree with root 5, left child 3, right child 8, and 3's left child 1.
- Common mistakeWhy doesn't level-order traversal ever revisit a node once that node is already sitting in the queue?
- Ties togetherHow does level-order traversal on a tree use the exact same queue idea that breadth-first search uses on a graph?
Your turn1 of 2
A level-order traversal visits a tree with 697 nodes spread across 13 depth levels, visiting every node at one depth before moving to the next. How many total node visits does the traversal make?Binary Search Tree Insert and Search
- How it worksHow does inserting into a BST compare a new value against each node and go left or right until it finds an empty spot?
- Worked exampleTrace inserting 5, 2, 8, 1, 3 in that order into an empty binary search tree.
- Common mistakeWhy isn't a binary search tree automatically laid out in memory the way a sorted array is?
Your turn1 of 2
Inserting 697 distinct values into an initially empty BST, one at a time, creates exactly n new nodes, one per insertion. How many total nodes does the BST have after all n insertions?Deleting from a Binary Search Tree
- How it worksHow does deleting a node with two children replace it with its inorder successor instead of just removing it?
- Worked exampleTrace deleting node 5 from a BST where 5's left subtree has a largest value of 4 and its right subtree's smallest is 6.
- Common mistakeWhy doesn't deleting a leaf node from a binary search tree ever require finding a replacement value?
- Going furtherWhat happens to a BST's shape once you delete its root node repeatedly until the tree is empty?
Your turn1 of 2
Deleting a leaf node from a BST of 142 nodes removes exactly 1 node, requiring no replacement value. How many nodes remain after deleting 6 separate leaf nodes one at a time?A BST Degenerating into a Linked List
- How it worksHow does inserting already-sorted data send every new node to the same side, one after another?
- Worked exampleTrace inserting 1, 2, 3, 4, 5 in that order and find why the resulting tree's height equals its node count.
- Common mistakeWhy isn't a binary search tree always fast just because it's called a search tree?
- Going furtherWhat happens to insert and search time once a degenerated BST holds a thousand nodes in a single chain?
- Ties togetherHow does a degenerated BST's shape become identical to the singly linked list built from the same values?
Your turn1 of 2
Inserting 697 values in already-sorted order into an empty BST sends every new node to the same side, one after another. What is the resulting tree's height, given the height equals the node count minus 1 in this degenerate case?Balanced Trees: Why an AVL Rotation Exists
- How it worksHow does a single rotation lift a deep node up and push its parent down to restore balance after an insert?
- Worked exampleTrace a right rotation that fixes a tree degenerated into a straight left-leaning chain of 3, 2, 1.
- Ties togetherHow does keeping a tree balanced preserve the log n search time that a degenerated BST loses entirely?
Your turn1 of 2
A single AVL rotation lifts one deep node up and pushes its parent down, fixing the balance after one insert. For 349 separate inserts that each trigger exactly one rotation, how many total rotations occur?