Introduction to Binary Trees
Imagine you're planning a treasure hunt in a large garden with numerous sections, each
offering two possible paths, one leading to the left and another to the right. At each section,
you can choose to explore another section to the left or the right. This method of organizing
your exploration, where each section leads you to two other choices (or ends the search),
closely mirrors the structure of a binary tree in computer science.
A binary tree is a structure that has a starting point (the first section in our analogy) and
branches out in such a way that each section (node) has at most two paths (children). This
structure is highly efficient for organizing and navigating data, making it a popular choice for
various computing tasks.
Tree Traversal
Continuing from our treasure hunt analogy, let's dive deeper into the concept of navigating
through these sections. Consider yourself not just an explorer, but a cartographer(a person
who draws or produces maps). Your mission is not only to explore sections but to map them.
Just as we have different paths and choices at each section, when dealing with binary trees
in computing, we have specific ways to traverse or visit each node (section) in the tree. This
process is akin to deciding on a route for your treasure hunt to ensure you explore all the
sections you want to map, capturing their details.
Imagine the following network where the starting point is Section-1, which is connected to
Section-2 and Section-3. Section-2 is connected with Section-4 & Section-5.
Let's explore these traversal methods:
First-Pass Route (Map the current section → Left Right):
In the "First-Pass Route, you start with your current location, Section 1, mapping and
recording it fully. Then, you proceed to explore and map the sections in a leftward direction,
moving to Section 2, then its left connection, Section 4, before Section 5. After completing
the left side, you journey to the right connections, visiting and mapping Section 3, followed
by Section 6, and finally, Section 7.
Example Journey:
1. Map Section 1.
2. Move left to Section 2, map it.
3. Continue left to Section 4, map it.
4. Back to Section 2.
5. Move right to Section 5, map it.
6. Back to Section 2, then to Section 1.
7. Move right to Section 3, map it.
8. Move left to Section 6, map it.
9. Back to Section 3.
10. Move right to Section 7, map it.
Mapping order: Section 1, Section 2, Section 4, Section 5, Section 3, Section 6, Section 7
In summary, you are doing the following:
Map the starting section.
Move to the left and map all sections in First-Pass Route order.
Back to the starting section.
Move to the right and map all sections in First-Pass Route order.
Question 1:
You are provided with a table that outlines the connections between a network of 14
sections. Your task is to determine the sequence in which you would map these sections
following the "First-Pass Route" strategy if you start from Section 8.
Next question part theory-
Left-to-Right Route
The "Left-to-Right route" begins by mapping the leftmost section first. Starting from Section
1, you travel left to City 2, then to the leftmost Section on this branch, Section 4, mapping it.
After Section 4, you return to map Section 2, and then Section 5. Having completed the left
expedition, you return to your starting point, Section 1, to map it, before heading right to
Section 3 then Section 6, and finally, Section 7, mapping each as you go.
Example Journey:
Starting from City 1,
Head left to Section 2
Head left to Section 4, map it
Return back to Section 2, map it
Head right to Section 5, map it
Return back to Section 2
Return back to Section 1, map it
Head right to Section 3
Head left to Section 6, map it
Return back to Section 3, map it
Head right to Section 7, map it
Painting Order: Section 4, Section 2, Section 5, Section 1, Section 6, Section 3, Section 7
To summarise, you will be doing the following
1. Head left from the starting Section and map all these Sections in Left-to-Right route order
2. Return back to the starting Section, map it
3. Head right from the starting Section and map all these Section in Left-to-Right route order
Question 2:
You are provided with a table that outlines the connections between a network of 14
Sections. Your task is to determine the sequence in which you would map these Section
following the "Left-to-Right route" strategy if you start from the city 9.
