Page 22: Introduction to Hierarchical Trees
Unlike lists or arrays, which store elements in a straight line, a Tree is a non-linear, hierarchical
data structure.
● The Concept: Data is categorized into groups and subgroups, organized like an
organizational chart. Nodes are connected to one another by lines called edges.
● Core Rule: A tree consists of nodes that have strict parent-child relationships.
● Computer Science Applications: File systems (folders and subfolders), network routing,
decision-making systems, and Binary Search Trees.
Page 23: Hierarchical Classifications & Subfolders
This page demonstrates how real-world data aligns naturally with tree architectures.
File Directory Analogy:
Think of your computer's storage layout. At the top sits a main directory folder (e.g., my stuff).
Inside, it splits into subfolders (home, work, play, school). Each subfolder can contain its own
specific files or further nested subfolders. Data appears at various distinct tiers within this
configuration.
Page 24: Core Tree Terminology
To answer exam questions accurately, you must learn the precise vocabulary used to describe
tree structures.
● Root: The unique, supreme node at the absolute top of the tree. It is the only node that
does not have a parent.
● Parent Node: A node that links directly down to other nodes beneath it. Except for the
root, every single node has exactly one parent.
● Child Node: A node linked directly from a parent node above it. A single parent can have
one or multiple children.
● Siblings: Nodes that share the exact same parent node.
● Internal Node: Any node that has one or more child nodes branching out from it.
Page 25: Leaves, Ancestors, and Descendants
This page covers structural relationships within a tree hierarchy.
● Leaf (External Node): A node sitting at the absolute end of a branch that has zero
children.
● Ancestor: An ancestor of a node includes its parent, grandparent, or great-grandparent
all the way up the chain. The root node is a universal ancestor to every other node in the
tree.
● Descendant: A descendant of a node includes its children, grandchildren, and any
subsequent nodes down that branch.
Page 26: Understanding Subtrees
● Subtree: A smaller tree nested completely inside a larger tree layout.
● Mechanics: You can take any child node in a tree and treat it as the root of its own
independent subtree. That subtree can be divided into even smaller subtrees down the
line.
Page 27: Tree Metrics: Depth and Height
This page details the math rules used to calculate tree levels and boundaries.
● Depth of a Node: The total number of ancestor steps above that node. The root node
always sits at a depth of 0.
● Height of a Tree: The maximum depth calculated down to the furthest leaf node. For
example, if the lowest leaf is at depth 3, the total tree height is 3.
● Adjacent Nodes: Two nodes are considered adjacent if an edge line connects them
directly.
Page 28: Defining Paths & General Trees
● Path: A specific structural sequence of nodes where each node is adjacent to the next.
● Path Length: The number of connecting edges along a path. For example, a path from
root A down to leaf I passing through node F (A -> F -> I) has a path length of 2.
● General Tree: A type of tree structure where any node can have an infinite number of
children.
Page 29: Binary Trees & Balanced Variations
● Binary Tree: A strict tree variant where no node can have more than two children. Every
node has a maximum of a left child and a right child.
● Full Tree: A configuration where every single leaf node sits on the exact same bottom
level.
● Complete Tree: A tree where every level is fully packed, and the bottom leaves are filled
progressively from left to right without skipping spaces.
Page 30: Structural Variations & Systemic Traversal
● Uncomplete Tree: A tree that breaks complete tree placement rules by leaving blank
spaces between bottom nodes.
● Skewed Binary Tree: A tree that slopes entirely in one direction, containing only left
children or only right children. It effectively functions like a sequential list.
● Similar Trees: Two separate trees that share the exact same structural shape but contain
different data values inside their nodes.
● Identical Trees: Trees that share the exact same structural shape and the exact same
data values.
● Traverse: The systemic process of visiting every single node in a tree exactly once.
Page 31: Implementation Layout for a Binary Node
This page outlines the foundational storage blueprint for coding a binary tree in C++.
struct Node {
Node* parent; // Pointer referencing the parent above
int data; // Stored value payload
Node* left; // Pointer referencing the left child branch
Node* right; // Pointer referencing the right child branch
};
I have hit the response length safety baseline for this turn. Reply with "Continue" when you are
ready, and we will break down the final section on Binary Search Trees (Pages 32–42) to finish
your exam review!