Ch 7. Key Terms

Acyclic (graph): A graph that contains no cycles

Ancestor: Any node on the (unique) path from a given node up to the root in a rooted tree.

Balanced tree: A tree whose height is kept proportional to [latex]\text{log } n[/latex] (e.g., via structural balance), giving logarithmic-time operations in BSTs.

Binary search tree (BST): A binary tree where each node’s left subtree contains keys less than the node’s key and the right subtree contains keys greater than it, recursively.

Binary tree: A rooted tree in which each node has at most two children (typically referred to as left and right).

Child: A node that descends directly from another node (its parent).

Connected (graph): A graph in which a path exists between every pair of vertices.

Decision tree: A hierarchical structure for conditional logic or classification

Descendant: Any node that lies below a given node in the hierarchy, including children and deeper nodes.

Full binary tree: A binary tree in which every internal vertex has exactly two children (nodes are either leaves or have two children).

Height (of a tree): The maximum level of any vertex; equivalently, the length (in edges) of the longest root-to-leaf path.

Hierarchical tree: A rooted tree used to model top-down relationships where each node has one parent and zero or more children (e.g., org charts, file systems).

In‑order predecessor: In a BST, the maximum key in a node’s left subtree.

In‑order successor: In a BST, the minimum key in a node’s right subtree.

In-order traversal: Visiting the left subtree, then the node, then the right subtree.

Internal vertex (branch): A node that has at least one child.

Terminal vertex (leaf): A node with no children.

Left child/Right child: The designated left or right child of a node in a binary tree.

Level (of a node): The number of edges from the root to the node.

Parent: A node that has one or more children.

Perfect binary tree: A binary tree where all internal nodes have two children and all leaves are at the same level.

Post-order traversal: Visiting the left subtree, then the right subtree, then the node.

Pre-order traversal: Visiting the node, then the left subtree, then the right subtree.

Root: The topmost node of a rooted tree.

Rooted tree: A tree with one designated root, from which every other node is reachable by a unique path.

Siblings: Nodes that share the same parent.

Subtree (of [latex]T[/latex] rooted at [latex]x[/latex]): The tree consisting of node [latex]x[/latex] and all of its descendants.

Tree: A connected, acyclic graph.

Tree sort: Sorting by inserting items into a BST and then outputting them via in-order traversal.

Unbalanced tree: A tree whose height can grow toward [latex]n - 1[/latex] (e.g., a chain), causing linear‑time operations in BSTs.