# Tree Flashcards

1
Q

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?

A

Hierarchically.

2
Q

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

A

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.

3
Q

Tree definition?

A

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

4
Q

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

A

5
Q

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

A

Vertices

6
Q

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

A

Edges

7
Q

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

A

Root Node.

8
Q

What is the definition of Child Vertices?

A

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

9
Q

What is a Parent Node?

A

Any node which has one or more child vertices.

10
Q

What is a Leaf Node?

A

A node which does not have any child vertices.

11
Q

Can a node be categorised as multiple different node types?

A

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

12
Q

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

A

Height is a property of a Tree

13
Q

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

A

Depth is a property of a Node

14
Q

Tree HEIGHT definition?

A

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.

15
Q

Node Depth definition?

A

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.

16
Q

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?

A

Rules and Restrictions

17
Q

What is a Binary Search Tree?

A

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)

18
Q

What are the three restrictions of a Binary Search Tree?

A
1. Each vertice 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.
19
Q

When are Binary Search Trees most useful?

A

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

20
Q

When are Binary Search Trees most useful?

A

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

21
Q

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.

A

implementations (hundreds)

22
Q

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

A

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

23
Q

What are two other names for a Trie?

A
1. Digital Trees
2. Prefix Trees
24
Q

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

A

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```
25
Q

What is the benefit of a Trie?

A

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.

26
Q

Why is a Trie called a Trie?

A

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

27
Q

Common use case for a Trie?

A

Auto-complete
Spell-check
Search Suggestions

28
Q

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’?

A

Flagging

29
Q

What is Flagging?

A

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.

30
Q

What is a AVL Tree?

A

AVL trees are a height balancing binary search tree.

31
Q

What is the maximum number of nodes in a binary tree of height k?

A

2k+1-1 where k >= 1

32
Q

Which data structure suits the most in the tree construction?

A

Queue

33
Q

Write the recursive C function to count the number of nodes present in a binary tree.

A

int count (struct node* t)
{
if(t)
{
int l, r;
l = count(t->left);
r=count(t->right);
return (1+l+r);
}
else
{
return 0;
}
}

34
Q

Write a recursive C function to calculate the height of a binary tree.

A

int countHeight(struct node* t)
{
int l,r;
if(!t)
return 0;
if((!(t->left)) && (!(t->right)))
return 0;
l=countHeight(t->left);
r=countHeight(t->right);
return (1+((l>r)?l:r));
}

35
Q

How can AVL Tree be useful in all the operations as compared to Binary search tree?

A

AVL tree controls the height of the binary search tree by not letting it be skewed. The time taken for all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the number of nodes.

36
Q

State the properties of B Tree.

A

A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.

Every node in a B-Tree contains at most m children.
Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
The root nodes must have at least 2 nodes.
All leaf nodes must be at the same level.

37
Q

List some applications of Tree-data structure?

A

Applications of Tree- data structure:

The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis
Hierarchal data model