Trees

Question 1

What is a tree ?

Answer 1

A tree is a data structure that is made up of a collection of nodes,
One root node, each node has zero or more children,
Edges or links connect parent and child nodes.

Question 2

What are the different tree properties ?

Answer 2

Depth of node - Number of edges between the root and that node,
Height of tree - Longest path from root to a leaf (node with no children),
Size - Total number of nodes.

Question 3

What is a binary tree ?

Answer 3

Each node has at most two children,
Defined recursively - Either empty, or a root with two binary subtrees.

Question 4

What are the types of binary trees ?

Answer 4

Full - Every node has 0 or 2 children,
Complete - All levels filled left to right except possibly the last,
Perfect - Complete tree with all leaves at the same depth,
Balanced - Height difference between left and right <= 1,
Degenerate - Each parent has only one child (linked list).

Question 5

What are the two types of tree traversal ?

Answer 5

Depth first search,
Breadth first search.