Introduction to Trees

By the end, you can

• Define a tree and state its two structural rules (one root, no cycles).
• Apply the N−1 edge formula to count edges given N nodes.
• Identify the root, leaves, internal nodes, siblings, parent, and subtree of any node.
• State the degree of a node.
• Calculate the depth of any node and the height of any node or the whole tree.
• Explain why depth and height are measured in opposite directions, and give the base cases (root depth = 0, leaf height = 0).
• Distinguish a tree from a linear structure and explain the O(log n) advantage of balanced trees.
• Name three real-world systems that use trees and describe how each uses the structure.