Lesson 12: Trees & binary search trees
Think of a family tree, or folders within folders: something 'on top' branches into items 'below'. That's a 'tree' — each point is a 'node'. In a 'binary search tree' (BST), every node has smaller values to its left and larger to its right — just like looking up a word in a dictionary: open the midd
A BST is like looking up a word in a dictionary: open the middle, and if the word comes 'earlier' you skip the entire right half at once. Each comparison saves half the work — but only if the pages are split evenly.
- class
- A template for a small box with fields. class TreeNode defines a box with three fields: val (the value) and left/right (the children). TreeNode(5) creates such a box, and self simply means "this box" (same idea as the linked-list lesson).
- binary search tree
- A binary tree where, for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
- tree traversal
- Visiting every node of a tree in a defined order. Inorder (left, node, right) on a BST yields the values sorted.
- balanced tree
- A tree whose height is about log n, so search takes O(log n). A skewed tree loses that advantage and reaches O(n).
