In computer science, the tree data structure is one of the most useful because it allows us to find information that is correctly sorted quickly. As you will see, organizing your data into a tree can drastically reduce the number of operations required to access the data.
Take it slow and understand fully.
Many of the algorithms and data structures you are working on have solutions to them. Studying the solutions is not a bad technique. However, it can be easy to read an answer and think you understand what is going on when you do not.
For this lesson, in particular, review each line of code and ensure you understand what is happening. Try adding a comment above each line of code, describing what is happening as fully as possible.
When going slow, it can be easy to beat yourself up about not understanding sooner. Please focus on the goal (i.e., understanding) instead of how long it's taking you to get there. Speed will come through practice!
- Look at the following code and guess what will be printed to the console.
const name = {
first: "Eleanor",
last: "Willows",
};
const address = {
line1: "493 Poplar St.",
line2: "Apt. 3A",
city: "New York City",
state: "NY",
};
console.log({ name, ...address });
console.log({ ...name, address });
console.log({ ...name, ...address });- Look at the following code and guess what will be printed to the console.
const people = [
{ first: "Owen", last: "Knight" },
{ first: "Raelynn", last: "Navarro" },
{ first: "Demi", last: "Porter" },
{ first: "Joe", last: "Davies" },
];
const friends = [];
friends.push(people.pop());
friends.push(people[1]);
people[1].first = "Rae";
console.log(friends);
console.log(people);Watch the following two videos and answer the questions below each one.
-
"Arrays and linked lists are linear data structures while a tree is not." What does this statement mean?
-
Define the following terms: root, node, link, edge, children, parent, sibling, leaf node, internal nodes, ancestor, descendant, depth, height
-
"Trees are recursive data structures." What does this statement mean?
-
What kind of data is best stored in trees?
- (Only watch up until the point where the code is on the screen, about four minutes.) Data Structures: Trees
-
How is a binary search tree different than a binary tree?
-
How can a binary search tree become unbalanced?
-
What is the benefit of using a balanced binary search tree when looking for data?
Next, complete the two exercises below this.
- Insert the numbers inside of the following array in order using the website linked below. Before you press the "insert" button, guess where each number will appear.
[11, 9, 13, 10, 7, 12, 14, 8, 3, 4, 6, 15, 5];- Consider the following questions about the array and the tree you created above:
-
If you were to search the array using linear search, how many operations are required to find the number 10?
-
If you were to search on the array using binary search, how many operations are required to find the number 10?
-
How many operations are needed to find the number 10 in the tree?
-
Answer the same questions above for the number 15. How do your answers compare?
To get better with trees, build a binary search tree. Follow the tutorial here to make one. To ensure you understand how the methods work, describe what each line of code does in comments above each line. Make sure to use your own words as opposed to copying and pasting.