Tree

Question 1

All other Data Structures covered so far store their data linearly (even the Map under the hood). How does a Tree/Graph store its data?

Answer 1

Hierarchically.

Question 2

What is a real-world example of a Hierarchical structure?

Answer 2

A Family Tree.
Each person would be an Element of the family tree and connections aren’t based on a simple linear fashion rather connections are more abstract and can lead to multiple paths or branches. Each generation is ordered on a HIERARCHY. There is no definitive end to a family tree. There may be several children at the bottom but which one of them is the definitive end? None.

A File Structure on a computer.
A folder which contains multiple files and folders which in turn can contain more folders and files.

Question 3

Tree definition?

Answer 3

An abstract Data Structure which contains a series of linked nodes connected together to form a hierarchical representation of information.

Question 4

The data for each element is stored in a Node along with its connections to other Nodes. This is similar to which data structure?

Answer 4

Linked List.

Question 5

In a Tree structure what is another name for a Nodes?

Answer 5

Vertices

Question 6

In a Tree structure, what are the connections between Node/Vertices called?

Answer 6

Edges

Question 7

What is the name of the top-most node of a Tree?

Answer 7

Root Node.

Question 8

What is the definition of a Child Node?

Answer 8

A node which has an Edge connecting it to another Node that is one level above itself.

Question 9

What is a Parent Node?

Answer 9

Any node which has one or more child nodes.

Question 10

What is a Leaf Node?

Answer 10

A node which does not have any child nodes.

Question 11

Can a node be categorised as multiple different node types?

Answer 11

Yes. E.g. A Child Node and a Leaf Node.

Question 12

Is the HEIGHT a property of a Tree or a Node?

Answer 12

Tree

Question 13

Is the DEPTH a property of a Tree or a Node?

Answer 13

Node

Question 14

Tree HEIGHT definition?

Answer 14

Number of edges on the longest possible path down towards a leaf. i.e. How many hierarchies in the tree, not including the Parent Node.

Question 15

Node Depth definition?

Answer 15

Number of edges required to get from that particular node to the root node. Think, depth under water, how far it has to go to get to the surface.

Question 16

Regular trees are great for storing hierarchical data, but their power can be really heightened when you start messing around with HOW the data is actually stored within them. What are the two R’s for HOW data can be stored in a Tree?

Answer 16

1. Rules

2. Restrictions

Question 17

What is a Binary Search Tree?

Answer 17

A tree where theres is natural ordered to how the data is stored which allows us to search through them in Logarithmic Time. O(log n)

Question 18

What are the three restrictions of a Binary Search Tree?

Answer 18

1. Each node can have at most two children.
2. For any given parent node, the child to the left has a value less than itself, and the child to the right has a value greater than itself.
3. No two nodes can contain the same value.

Question 19

When are Binary Search Trees most useful?

Answer 19

When storing large quantities of data that need to be quickly searched.

Question 20

When are Binary Search Trees most useful?

Answer 20

When storing large quantities of data that need to be quickly searched.

Question 21

A Tree’s base structure is incredibly useful and it can be modified in so many ways to add to its functionality which leads to many different … for varying use cases.

Answer 21

implementations (hundreds)

Question 22

A Trie is an implementation of a Tree. What is a Trie’s definition.

Answer 22

A Trie is a tree-like data structure whose nodes store letters of an alphabet in the form of characters.

Question 23

What are two other names for a Trie?

Answer 23

1. Digital Trees

2. Prefix Trees

Question 24

A Trie is an implementation of a Tree. What is a Trie’s definition.

Answer 24

A Trie is a tree-like data structure whose nodes store letters of an alphabet in the form of characters.

           Root
       |              |
      d             h
    |      |       |      |
  de   do   ha    he
                          |
                          hen

Question 25

What are two other names for a Trie?

Answer 25

1. Digital Trees

2. Prefix Trees

Question 26

What is the benefit of a Trie?

Answer 26

It allows us to quickly retrieve (reTRIEve!) words in the form of String by traversing down a path of the trie in a certain way.

In layman’s terms, we use Tries to retrieve words extremely fast by traversing down a tree of stored characters.

Question 27

Why is a Trie called a Trie?

Answer 27

Because it’s main benefit is retrieving words. re-trie-ving words… reTRIEve, TRIE!

Question 28

Common use case for a Trie?

Answer 28

Auto-complete
Spell-check
Search Suggestions

Question 29

How does a Trie now that it has hit the end of a word? E.g. A branch contains d-e-n-v-e-r. How do we know when we’re at the ‘n’ node that we’ve made a complete word, in this case, ‘den’?

Answer 29

Flagging

Question 30

What is Flagging?

Answer 30

Marking the end of a word by having its node also point towards a “flag” value to let the computer know that the end of a word has occurred. The flag can be whatever you want, the period (full stop) ‘.’ character is a good choice.

I’m sure you could use Flagging for other uses too. Like marking a word as a plural. This might be useful for auto-complete if the words leading up to the one you are currently typing suggest that you want to type the plural version of the word in which case the auto-complete would likely suggest that instead of the singular.

Question 31

What is a AVL Tree?

Answer 31

AVL trees are a height balancing binary search tree.