5.1 Tree Terminology and Properties

Tree Fundamentals

Trees are the go-to data structure for representing hierarchical relationships. A tree is made up of nodes connected by edges, where each node stores data and references to other nodes. If you've ever looked at a file system, an org chart, or an HTML document, you've seen a tree structure in action.

This section covers the core terminology and properties you'll need before working with binary trees, BSTs, and tree algorithms.

Fundamental Concepts of Trees

A tree is a hierarchical, acyclic data structure. "Acyclic" means there are no cycles: you can't start at a node, follow edges, and end up back where you started. Edges are directed, always pointing from a parent down to a child.

Here's the key vocabulary for the parts of a tree:

• Node: the basic unit in a tree, storing data and references to other nodes
• Root node: the topmost node in the tree; it has no parent
• Parent node: a node that directly connects to and sits above another node
• Child node: a node that directly connects to and sits below another node
  • Sibling nodes: nodes that share the same parent
• Leaf (external node): a node with zero children
• Internal node: a node with at least one child
• Edge: a connection between two nodes, representing a parent-child relationship
• Subtree: any node in the tree together with all of its descendants; every node is the root of its own subtree

One property worth remembering: a tree with $n$ nodes always has exactly $n - 1$ edges. This follows directly from the fact that every node except the root has exactly one incoming edge from its parent.

Properties and Characteristics of Trees

These numeric properties show up constantly in algorithm analysis, so make sure you can distinguish them:

• Depth of a node: the number of edges from the root down to that node
  • Nodes at the same depth are said to be on the same level
  • The root is at level 0, its children at level 1, and so on
• Height of a node: the number of edges on the longest path from that node down to a leaf
  • A leaf node has height 0
• Height of a tree: the height of the root node, which equals the maximum depth of any node in the tree
• Degree of a node: the number of children that node has
• Degree of a tree: the maximum degree of any node in the tree

Tree Types and Relationships

Types of Trees

Binary trees restrict each node to at most two children, called the left child and right child. Two important variants:

• Strict (proper) binary tree: every node has either 0 or 2 children. No node has exactly one child.
• Complete binary tree: every level is fully filled except possibly the last, and the last level has all its nodes packed as far left as possible. This is the shape you see in a binary heap.

A binary search tree (BST) is a binary tree that enforces an ordering rule:

1. Every node in the left subtree has a key less than the current node's key.
2. Every node in the right subtree has a key greater than the current node's key.
3. Both the left and right subtrees are themselves valid BSTs.

This ordering is what makes search efficient: at each node, you can eliminate an entire subtree.

A balanced tree keeps the height difference between the left and right subtrees of any node to at most one. AVL trees and Red-Black trees are classic examples. Balancing guarantees $O(\log n)$ time for search, insertion, and deletion, whereas an unbalanced BST can degrade to $O(n)$ in the worst case (think of inserting sorted data into a plain BST, which produces a straight chain of nodes).

Relationships Between Tree Nodes

• Path: a sequence of nodes connected by edges from an ancestor down to a descendant. The path length is the number of edges in that sequence.
• Distance: the number of edges on the (unique) path between two nodes.
• Lowest Common Ancestor (LCA): the deepest node that is an ancestor of both given nodes. The LCA is useful for computing the distance between two nodes: find the LCA, then add the distance from the LCA to each node.

Traversal means visiting every node in the tree exactly once, in a defined order. For binary trees, the three standard depth-first traversals are:

1. Preorder (Root → Left → Right): visit the current node first, then recurse into the left subtree, then the right subtree.
2. Inorder (Left → Root → Right): recurse into the left subtree, visit the current node, then recurse into the right subtree. For a BST, inorder traversal visits nodes in sorted (ascending) order.
3. Postorder (Left → Right → Root): recurse into the left subtree, then the right subtree, then visit the current node. This is useful when you need to process children before their parent (e.g., deleting a tree or evaluating an expression tree).