# Define Rules.

- Set of nodes and edges that connect them.
- excatly one path between the nodes.
- Path = connected sequences of edges.
- Edges = connecting nodes

`Rooted Tree`

- Every Node has a parent, except Root.
- One Node can have any number of childern.

# Definitions

- Leaf = Node with no children.
- Siblings = Nodes with same parents.
- Ancestors = nodes on the path from node(d) to root, including node(d) itself.
- If a is ancestor of node d, then node d is descendant of node a.
- Length = # of edges in path.
- Depth of a node = length of path from n to root.
- (depth of root is 0 )

- Height of the node = length of path from n to its deepest descendant.
- Height of any leaf is 0.
- Height of tree = Height of the root.

- SubTree rooted at N : tree formed by n and its descendants.
- Binary Tree
- No node has more than 2 children ( > 2)
- Every Child is either left or right child, even if its the only child.

# Representing Rooted Trees

- one way = item,parent,children stored in a list
- another option = siblings are directly connected.

```
class Node{
Object item;
Node parent;
Node firstChild;
Node nextSibling; // this can become singly linked list
// nextsibling can keep track so a node can have many //childs. Essentially a singly linked list with first child as head of LL.
}
class Tree {
Node root;
int size;
}
```

# Traversal

- Visiting the node once.

### Frequent Traversal

##### Preorder Traversal

```
- Visit each node before recursively visiting its children
- Left to Right
- Root Visited First
- Visited only once
- Takes O(N) for entire traversal - Linear Time
```

```
class Node {
public void preorder(){
this.visit();
if(firstChild!=null){
firstChild.preorder();
}
if(nextSibiling !=null){
nextSibling.preorder();
}
}
}
```

Visualize Preorder Traversal. Order of processing.

```
1
2 6
3 4 5 7 8
```

##### PostOrder Traversal

- Visit each node children before node itself
- Left to Right
- Natural way to sum total disk space ( use case )
- First get the subdirectories then the parent and then entire filesystem

```
public void postorder(){
if(firstchild !=null){
firstChild.postorder();
}
this.visit();
if(nextsibling !=null){
nextsibling.postorder();
}
}
```

Visualize

```
8
4 7
1 2 3 5 6
```

- Children gets visited first
- Then the node
- Finally the root.

##### InOrder Traversal ( only in Binary Trees )

- Visit the left child
- then Visit the node itself
- then Visit the Right child.
- Natural for parsing the expression tree.
- O(N) - Linear Time.

Visualize parsing the expression tree.

```
+
* ^
3 7 4 2
```

`In Order`

: 3 * 7 + 4 ^ 2 ( easy for human to read )`Post order`

: 37 * 42 ^ +`Pre Order`

: + * 37 ^ 42 (easy for computer )

##### Level order Traversal

- Visit Root, then all depth-1 nodes
- then depth-2 , ... depth-n
- so for above expression => +*^ 3742
- not recursive
- will use queue which initially contains only the root.
- repeat below steps , until queue is empty.
- dequeue a node
- visit that node
- enqueue the children ( Left to Right )