# # Trees

- Trees data structure can represent some form of hierarchy
- A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more sub-trees.
- Tree is a
**acyclic**connected graph- If not connected, could be a
**forest**

- If not connected, could be a

Tree Definition

For every tree

proof by Induction

where,

- Isomorphic Trees
- Greek "same shape", 2 trees with same number of nodes, edges might have different connections
- Vertices
- set of all Nodes for a given tree T
- Edges
- ordered-pair of set of connecting nodes in the associative Array format (generally).
Eg:
`{(a,b), (b,c), (a,c)}`

Graphs

All Trees are graphs, but all graphs are **not** tree.

why? because trees are **Acyclic**, meaning cannot have cycles

- Cayley's formula
- Calculate how many trees could be formed from given number of nodes

### # Memory Representation of Tree

- Linear using Array
- Linked Lists using pointers

#### # Linear using Array

Element | formula |
---|---|

Root Node | |

Left Child | |

Right Child | |

Parent |

Example: To Do

text

Always analyze your solution, space time complexity

- Function to implement unival trees?
- How to implement auto-completion?
- K-th largest number
- Brute force technique
- Improve your solution

### # Operations on trees

#### # Traversal

- BFS Breadth first Search
- DFS Depth First Search