Trees
Lists and queues keep values in a row. A tree branches instead: each node links down to children, from one root at the top to the leaves at the bottom. Meet the parts of a tree, see the trees you already use, then watch a binary search tree find 60, insert 35 and list every value in sorted order.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01In a tree, what is a leaf?
Leaves are the nodes at the ends of the branches: they have no children. The top node, the only one with no parent, is the root.
02In the binary search tree 50 (root), 30, 70, 20, 40, 60, 80, which nodes does a search for 40 visit?
Start at the root. 40 is smaller than 50, so go left to 30. 40 is larger than 30, so go right, and there is 40.
03Where does inserting 65 into that same tree put the new node?
65 > 50: go right to 70. 65 < 70: go left to 60. 65 > 60: go right. That spot is empty, so 65 becomes the right child of 60.
04You insert 1, 2, 3, 4, 5 into an empty binary search tree, in that order. What shape do you get?
Each new value is larger than everything before it, so it always goes right. The tree becomes a line, and a search may have to check every node.
05What does an in-order traversal of a binary search tree produce?
In-order visits the left subtree, then the node, then the right subtree. In a binary search tree everything left is smaller and everything right is larger, so the values come out sorted.
Glossary
- Node
- One item in a tree. It holds a value and links to its children.
- Root
- The top node of a tree: the only node with no parent.
- Leaf
- A node with no children.
- Parent and child
- A node links down to its children; each child has exactly one parent.
- Depth and height
- A node's depth is the number of links from the root down to it. A tree's height is its largest depth.
- Binary search tree
- A binary tree where, at every node, the left subtree holds only smaller values and the right subtree only larger ones.
- Traversal
- Visiting every node of a tree once. In-order visits the left subtree, then the node, then the right subtree.
- O(log n) and O(n)
- Ways to say how the work grows with n values: with the number of levels (about log2 of n) or in step with n itself.
Notes and sources
- O(log n), read "order log n", means the work grows like the logarithm of n: doubling the number of values adds about one more comparison. O(n) means the work grows in step with n.
- A plain binary search tree only stays balanced if the values arrive in a mixed-up order. Self-balancing trees, such as red-black trees and AVL trees, reshape themselves on every insert so the height stays about log2(n).
- A full tree with 20 levels holds 2^20 - 1 = 1,048,575 nodes, and a search compares at most once per level.
- This insert sends a value equal to a node's key to the right. Many libraries instead refuse duplicates or keep a count.
- Strictly, the browser builds the DOM tree from HTML and fills in parts the page leaves out, such as a missing head or body.
- Sedgewick and Wayne, Algorithms 4th ed.: 3.2 Binary Search Trees
- Sedgewick and Wayne, Algorithms 4th ed.: 3.3 Balanced Search Trees
- MIT OpenCourseWare 6.006 Introduction to Algorithms (Spring 2020)
- Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th ed. (MIT Press)
- Python tutorial: Classes
- Python library: os.walk (a directory tree)
- Python library: xml.etree.ElementTree
- MDN: Introduction to the DOM
- WHATWG DOM Standard: Trees
Quiz Unlocks after the last step.