Why Hierarchies Represent Nested Relationships

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 12.1 Free with a free account

Why Hierarchies Represent Nested Relationships

Data Structures and Algorithms · Chapter 12: TreesSection 12.1 · lesson 49 of 8712 min · free with a free account

← Rearranging Positional Collections into OrderNext lesson: Binary Trees: Structure, Properties, and Traversals →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How trees model belonging with roots, parents, children and subtrees.

  • Define a tree by its single root, single-parent and no-cycle rules
  • Measure a node's depth, height and subtree size by counting edges and nodes
  • Compare child lists, parent arrays and first-child next-sibling storage
  • Explain why nested lookups in a tree cost depth rather than total entries

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,772 words). Read along, or search it.

Opening Question

The Mail Carrier's Shortcut

A letter addressed to a house in another country reaches it, and no mail carrier ever looks at every house in the world. The address names a country, then a state, then a city, a street, and finally a house. Each part narrows the search to one branch, and every other branch is ignored. That only works because places are nested. Every house belongs to a street, and every street to a city. So here's the question for this lesson: when data is nested like that, what does storing it as a hierarchy actually buy you?

Why Trees

Data Built for Belonging

A lot of the data programs handle has this shape. Folders sit inside folders, employees report to managers, and sections of a report hold smaller sections. Arrays and linked lists line items up, one after another. They can say what comes next, but not what something belongs to. A tree can. It's built for belonging.

Definition

Three Rules That Make a Tree

A tree is made of nodes, the items that hold the data, and edges, the links between them. Each edge joins a parent above to a child below. Three rules turn linked nodes into a tree. One: exactly one node has no parent. That's the root, and it sits at the top. Two: every other node has exactly one parent. Three: there are no cycles. Climbing from any node, parent by parent, always ends at the root. Notice the tree is drawn upside down, root on top, because that's how people read a hierarchy.

Worked Example

A File System as a Tree

Here's a small file system, drawn as a tree. The folder called root is the root of the tree. Inside it are three folders. Inside home are two users' folders, ana and ben, and so on, all the way down to the files. Home is the parent of ana and ben, and they are its children. Nodes that share a parent are siblings, like notes.txt and photos.

Vocabulary

Leaves, Ancestors and Subtrees

A node with no children is a leaf. This tree has six of them: notes.txt, the two pictures, todo.txt, hosts, and java. A node with at least one child is an internal node, like home, ana, photos, or bin. Anything above a node, on its path to the root, is an ancestor. Anything below it is a descendant. And a subtree is a node together with all its descendants. Home and everything under it form one subtree.

Key Fact

Fourteen Nodes, Thirteen Edges

Count the boxes and the lines. Fourteen nodes, and thirteen edges. That's no accident. Every node except the root has exactly one parent, and each parent link is one edge. So a tree with n nodes always has n minus one edges. Give some node two parents, or a loop, and it's no longer a tree. It's a more general network, called a graph.

Measurements

Depth, Height and Size

Three measurements say where a node sits, and how big the branch under it is. Each one counts edges, not nodes. Depth is the number of edges from the root down to the node. The root has depth zero. Height is the number of edges on the longest path from the node down to a leaf. A leaf has height zero. And size is the number of nodes in the node's subtree, counting the node itself. The height of the whole tree is the height of its root, which is also the greatest depth of any node.

Worked Example

Measuring the Photos Folder

Try it on the photos folder. From root, the path goes home, ana, photos: three edges, so photos has depth three. Its longest path down reaches a picture in one edge, so its height is one. Its subtree holds photos and two pictures: size three. At the top, root has depth zero and height four. The subtree of home holds eight nodes: home itself, plus seven below it. The classic slip is counting nodes instead of edges. That makes every depth and height one too large.

In Code

Answers Built From the Children

In code, each node keeps a list of its children, and size and height are built the same way the tree is: from the children's answers. A node's size is one, for itself, plus the sizes of all its children. A leaf has no children, so its size is one. A node's height is the largest of one plus each child's height. With no children, the answer stays zero. Depth goes the other way. The search carries a counter down from the root, and adds one at every step.

Quick Check

Depth, Height and Size of Node C

Quick check, on a new tree. A is the root. B and C are its children. C has two children, D and E, and E has one child, F. What are the depth, the height and the size of node C? Pause, and decide. It's a: depth one, height two, size four. One edge separates C from the root. Its longest path down goes through E to F, two edges. And its subtree holds C, D, E and F. Option b mixes up depth and height. Option c counts the nodes on the path to F instead of the edges, and misses a node of the subtree.

General Trees

Child Lists for Any Number of Children

In a general tree, also called an n-ary tree, a node may have any number of children: none, one, three, or a hundred. Home had two children, while ben had one. That freedom fits real hierarchies, and it makes storage a little harder. Take this tree of seven nodes, numbered zero to six. The first design gives every node a list of its children. Asking for B's children just reads B's list: E and F, in two steps. But asking for F's parent means searching the lists, because no node stores its parent.

Storage Design

One Parent Index per Node

The second design uses the rule that every node but the root has one parent. Store one number per node: the index of its parent. The root stores minus one, which is not a valid index. Finding a parent is one array read, and climbing to the root is a short loop. The weak point is going down. Nothing points to children, so finding B's children means checking all seven entries.

Storage Design

First Child and Next Sibling Links

The third design gives every node exactly two links, however many children it has: its first child, and its next sibling. To list A's children, go to its first child, B, then follow sibling links: C, then D, then minus one, which means stop. Child lists and first child links both find B's children in two steps, where the parent array needed seven. In the other direction, the parent array wins. And the third design has a bonus: any tree can be stored with just two links per node. That idea leads straight to binary trees, where a node has at most two children.

Quick Check

Finding Children in a Parent Array

Quick check. A different tree is stored as a parent array: minus one, zero, zero, one, one, two. Which nodes are the children of node one? Pause, and decide. It's b: nodes three and four. Their entries hold a one, so node one is their parent. To find them, every entry had to be read: that's the parent array's weak direction. Option a lists node one's own parent and sibling. And going up is easy: node five's parent is two, and two's parent is zero.

Everyday Examples

Folders, Org Charts and Documents

Once you know the shape, trees are everywhere. A file system: a folder contains files and folders. An org chart: a manager supervises employees. A document: a section contains subsections. Each has one node at the top, and every other node under exactly one parent. Web pages, store categories and program packages work the same way.

Shared Code

One Method for Every Hierarchy

Because the shape is the same, the same code works on all three. A manager's subtree size, minus one for the manager, counts everyone in that reporting line. Here, the CEO's subtree has six people, so five sit below. Dev is a leaf: nobody reports to that role. And section numbers are paths. Two point one means the first child of the root's second child. An outline printer builds each number from its parent's number on the way down.

Comparison

Flat Path List Versus Tree Lookup

Now the payoff. Nothing stops you storing folders as one flat list of full paths, like d3/d7/d2. Everything is still there. To compare fairly, build a tree where every folder has ten children, and store the same entries both ways. Then ask three questions. First: find one entry by its path. The flat list scans from the start. The tree reads the path one name at a time, checking only that folder's ten children. With a hundred ten entries, the flat list needs a hundred ten comparisons, and the tree twenty. Make the data a hundred times larger, and the tree only climbs to forty.

Key Insight

Each Step Discards Other Branches

Why? Every step down the tree throws away every branch except one. Here, the first step discards nine tenths of all the entries at once. So the work grows with the depth of the tree, not with the number of entries. That's the mail carrier's trick, in code.

Comparison

Listing and Renaming a Folder

Second: list everything under the folder d3/d7. The flat list has no choice but to test every entry's text, all 1,110 of them, to find eleven. The tree walks to the folder in twelve comparisons, then visits exactly eleven entries: the folder, and the ten inside it. The work follows the size of the answer. Third: rename that folder. In the flat list, every path that starts with it must be rewritten: eleven here, and thousands for a big folder. In the tree, a child never stores its parent's name, so exactly one name changes, and everything below follows.

Limits

When a Hierarchy Is Not Needed

A hierarchy isn't always the answer. A list of customer names has no containment, so a plain list is simpler, and just as good. And for exact lookups by a single key, a hash table, coming later in the course, finds a full path quickly without any tree. What those can't do cheaply is answer the nesting questions: what's inside this, what is this inside of, and move this whole branch.

Key Takeaways

Rules, Measures and Storage Choices

To recap. A tree has one root, every other node has exactly one parent, there are no cycles, and n nodes means n minus one edges. Depth counts edges up to the root, height counts edges down to the deepest leaf, and size counts a subtree's nodes. A general tree can be stored with child lists, a parent array, or first child and next sibling links, and each favors different questions. And a tree narrows the search one level at a time, so nested questions cost depth, not the total count.

Think About It

Departments Stored as a Flat List

Here's something to think about. A designer stores a company's departments and teams as a flat list of team names, each with a column naming its department. What questions become slow? And what exactly would a tree add?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Why Hierarchies Represent Nested Relationships

What makes a data structure a tree rather than a graph?
A tree has exactly one root with no parent, every other node has exactly one parent, and there are no cycles, so climbing parent by parent from any node ends at the root. Because each non-root node contributes one parent edge, a tree with n nodes has n - 1 edges. Giving a node two parents or adding a loop breaks these rules, and the structure becomes a more general graph.
What is the difference between depth and height of a node in a tree?
Depth counts the edges from the root down to the node, so the root has depth 0. Height counts the edges on the longest path from the node down to a leaf, so a leaf has height 0. The height of the whole tree equals the root's height, which is also the greatest depth of any node. A common slip is counting nodes instead of edges, which makes each value one too large.
How do you compute the size of a subtree recursively?
A node's size is 1 for itself plus the sizes of all its children, so a leaf has size 1. In Java, if each node keeps a list of children, the method can be: int size(Node n) { int s = 1; for (Node c : n.children) s += size(c); return s; }. Height follows the same pattern: take the largest value of 1 plus a child's height, starting from 0 when there are no children.
What is a parent array representation of a tree?
A parent array stores one integer per node: the index of that node's parent, with -1 for the root. Finding a parent is one array read, and climbing to the root is a short loop. Finding children is slow, because every entry must be checked. For the array -1, 0, 0, 1, 1, 2, node 1's children are nodes 3 and 4, and node 5's parent is 2, whose parent is 0.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →