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 Child Vertices?

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 vertices.

Question 10

What is a Leaf Node?

Answer 10

A node which does not have any child vertices.

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

Height is a property of a Tree

Question 13

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

Answer 13

Depth is a property of a 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

Rules and 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 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.

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 is the benefit of a Trie?

Answer 25

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 26

Why is a Trie called a Trie?

Answer 26

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

Question 27

Common use case for a Trie?

Answer 27

Auto-complete
Spell-check
Search Suggestions

Question 28

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 28

Flagging

Question 29

What is Flagging?

Answer 29

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 30

What is a AVL Tree?

Answer 30

AVL trees are a height balancing binary search tree.

Question 31

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

Answer 31

2k+1-1 where k >= 1

Question 32

Which data structure suits the most in the tree construction?

Answer 32

Queue

Question 33

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

Answer 33

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;
}
}

Question 34

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

Answer 34

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));
}

Question 35

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

Answer 35

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.

Question 36

State the properties of B Tree.

Answer 36

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.

Question 37

List some applications of Tree-data structure?

Answer 37

Applications of Tree- data structure:

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