# Trees
Trees are a collection of nodes/vertices and edges(links) where one node is the root and the rest of the nodes are divided into disjoint subsets which are themselves trees or sub-trees. If there are `n` nodes, then there will be `n-1` edges. Every node has an edge coming towards it, except the root node(A).
```graphviz
digraph D
{
edge[dir=none]
node[shape=circle]
A -> {B, C, D}
B -> {E, F}
D -> {G, H, I}
F -> {J, K}
J -> M
H -> L
L -> {N, O}
}
```
## Terminology
### 1. Root
It is the node which is at the first level of the tree.
`A` is the root of the above tree.
### 2. Parent
A node is a parent of its descendants if it is connected by a single edge.
`B` is the parent of `E` and `F`.
### 3. Child
A node is a child of its ancestor if it is connected by a single edge.
`E` and `F` are children of `B`.
### 4. Siblings
Siblings are nodes which are children of the same parent.
`E` and `F` are siblings because they have the same parent `B`.
### 5. Descendants
They are a set of nodes which can be reached through a particular node. All the nodes under a particular node and are connected to it somehow are its descendants.
`E`, `F`, `J`, `K` and `M` are descendants of `B`.
### 6. Ancestors
For any node, all the nodes along the path of that particular node to the root are its ancestors.
For `M`, `J`, `F`, `B`, `A` are its ancestors.
### 7. Degree of a node
It is the number of children or direct descendants.
For `B`, the degree is 2.
### 8. Internal/External node
Nodes with degree zero are called external/terminal/leaf nodes. And the nodes with degree > 0 are internal/non-terminal/non-leaf nodes.
`E`, `M`, `K`, `G`, `N`, `O`, `I` are leaf nodes and all the other nodes are internal nodes.
### 9. Level
Level is the no. of nodes from root to that particular nodes level.
`H` is at level 3 as three nodes are in its path from root(`A`,`D`,`H`).
### 10. Height
### 11. Forest
Collection of trees is called forest.
Removing the root from the earlier tree gives us a forest.
```graphviz
digraph D
{
edge[dir=none]
node[shape=circle]
B -> {E, F}
C
D -> {G, H, I}
F -> {J, K}
J -> M
H -> L
L -> {N, O}
}
```
## Binary Tree
A tree of degree 2 is known as a Binary Tree. Degree of a tree is the maximum number of children a node can have. Therefore, in a binary tree any node can have at max 2 children.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
### Number of Binary Trees
If some number of nodes are given, find the different binary trees that can be generated. There are two types of nodes
1. Unlabelled nodes
2. Labeled nodes
and both will have different values.
#### 1. Unlabelled nodes
For n = 3, there can be 5 unique binary trees that can be generated.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label="",color=invis]
5[label="",color=invis]
1 -> 2
1 -> 4 [color=invis]
2 -> 3
2 -> 5 [color=invis]
6[label=""]
7[label=""]
8[label="",color=invis]
9[label="",color=invis]
10[label=""]
6 -> 7
6 -> 9 [color=invis]
7 -> 8 [color=invis]
7 -> 10
11[label=""]
12[label=""]
13[label=""]
11 -> {12, 13}
14[label=""]
15[label="",color=invis]
16[label=""]
17[label=""]
18[label="",color=invis]
14 -> 16
14 -> 15 [color=invis]
16 -> 18 [color=invis]
16 -> 17
19[label=""]
20[label="",color=invis]
21[label=""]
22[label="",color=invis]
23[label=""]
19 -> 21
19 -> 20 [color=invis]
21 -> 22 [color=invis]
21 -> 23
}
```
$T(3) = 5$
If T was a function that takes no. of nodes and gives the no. of trees as output.
F
$T(4) = 14$
The function T is given by the formula famously known as **Catalan's number**,
$$
T(n) = \frac{^{2n}C_{n}}{n+1}
$$
We can find it for n = 5 as,
$$
T(5) = \frac{^{2*5}C_{5}}{5+1} = \frac{^{10}C_{5}}{6} = 42
$$
Another way to calculate Catalan's number is by,
| | | | | | | | |
| -------- | --- | --- | --- | --- | --- | --- | --- |
| **n** | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| **T(n)** | 1 | 1 | 2 | 5 | 14 | 42 | |
$$
\begin{aligned}
T(6) & = T(0)*T(5) + T(1)*T(4) + T(2)*T(3) + T(1)*T(4) + T(5)*T(0) \\
& = 132 \\
T(n) &= \sum_{i=0}^n T(i-1)*T(n-i)
\end{aligned}
$$
**Maximum height** for the trees would be given by $2^{n-1}$. For n = 3, max height would be 4
.
#### 2. Labeled Nodes
For labeled nodes, for every unique binary tree there would be $n!$ permutations.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label="A"]
2[label="B"]
3[label="C"]
4[label="",color=invis]
5[label="",color=invis]
1 -> 2
1 -> 4 [color=invis]
2 -> 3
2 -> 5 [color=invis]
6[label="A"]
7[label="C"]
8[label="B"]
9[label="",color=invis]
10[label="",color=invis]
6 -> 7
6 -> 9 [color=invis]
7 -> 8
7 -> 10 [color=invis]
11[label="B"]
12[label="A"]
13[label="C"]
14[label="",color=invis]
15[label="",color=invis]
11 -> 12
11 -> 14 [color=invis]
12 -> 13
12 -> 15 [color=invis]
16[label="B"]
17[label="C"]
18[label="A"]
19[label="",color=invis]
20[label="",color=invis]
16 -> 17
16 -> 19 [color=invis]
17 -> 18
17 -> 20 [color=invis]
21[label="C"]
22[label="A"]
23[label="B"]
24[label="",color=invis]
25[label="",color=invis]
21 -> 22
21 -> 24 [color=invis]
22 -> 23
22 -> 25 [color=invis]
26[label="C"]
27[label="B"]
28[label="A"]
29[label="",color=invis]
30[label="",color=invis]
26 -> 27
26 -> 29 [color=invis]
27 -> 28
27 -> 30 [color=invis]
}
```
Therefore, Catalans number changes to,
$$
T(n) = \frac{^{2n}C_{n}}{n+1}*n!
$$
The first part gives us the no. of binary trees and the second part is used for filling those trees.
### Height vs Nodes
We can find the minimum and maximum number of nodes to form a binary tree if we know its height.
$$
\begin{aligned}
\text{Min nodes } & n = h + 1 \
\text{Max nodes } & n = 2^{h+1}-1
\end{aligned}
$$
We can find the max and min height of a binary tree if we know the number of nodes.
$$
\begin{aligned}
\text{Min height } & h = log_2(n+1)-1 \
\text{Max height } & h = n - 1
\end{aligned}
$$
### Internal vs External nodes
There is a relationship between the nodes with degree of 2 and nodes with degree of 0.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
6[label=""]
7[label=""]
1 -> {2, 3}
2 -> {4, 5}
4 -> 6
5 -> 7
}
```
$deg(2) = 2$
$deg(1) = 2$
$deg(0) = 3$
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
6[label=""]
7[label=""]
8[label=""]
9[label=""]
10[label=""]
11[label=""]
12[label=""]
1 -> {2, 3}
2 -> {4, 5}
4 -> 6 -> 7 -> 8
3 -> {9, 10}
9 -> 11
10 -> 12
}
```
$deg(2) = 3$
$deg(1) = 5$
$deg(0) = 4$
**The relation is $deg(0) = deg(2) + 1$**
## Strict Binary Trees
It is a binary tree where each node can have either 0 or 2 children and cannot have 1 child.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
1 -> {2, 3}
3 -> {4, 5}
}
```
### Height vs Nodes
We can find the minimum and maximum number of nodes to form a strict binary tree if we know its height.
$$
\begin{aligned}
\text{Min nodes } & n = 2h + 1 \
\text{Max nodes } & n = 2^{h+1}-1
\end{aligned}
$$
We can find the max and min height of a binary tree if we know the number of nodes.
$$
\begin{aligned}
\text{Min height } & h = log_2(n+1)-1 \
\text{Max height } & h = \frac{n - 1}{2}
\end{aligned}
$$
### Internal vs External
There is a relationship between internal and external nodes in a strict binary tree.
$\text{External nodes} = \text{Internal nodes} + 1$
## n-ary Trees
They are trees with degree n i.e maximum number(or capacity) of children it can have is n.
eg: **3-ary trees**
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
6[label=""]
7[label=""]
8[label=""]
9[label=""]
1 -> {2, 3, 4}
2 -> {5, 6}
4 -> {7, 8, 9}
}
```
**4-ary trees**
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
6[label=""]
7[label=""]
8[label=""]
9[label=""]
1 -> {2, 3}
2 -> {4, 5, 6, 7}
3 -> {8, 9}
}
```
## Strict n-ary tree
In this tree, every node must have either 0 or exactly n children.
example: **strict 3-ary tree**
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
1[label=""]
2[label=""]
3[label=""]
4[label=""]
5[label=""]
6[label=""]
7[label=""]
1 -> {2, 3, 4}
2 -> {5, 6, 7}
}
```
### Height vs Nodes
We can find the minimum and maximum number of nodes to form a strict m-ary tree if we know its height.
$$
\begin{aligned}
\text{Min nodes } & n = mh + 1 \
\text{Max nodes } & n = \frac{m^{h+1}-1}{m-1}
\end{aligned}
$$
We can find the max and min height of a strict m-ary tree if we know the number of nodes.
$$
\begin{aligned}
\text{Min height } & h = log_m[n(m-1)+1]-1 \
\text{Max height } & h = \frac{n - 1}{m}
\end{aligned}
$$
$m$ is used here to represent the degree of the tree and to avoid confusion with $n$ which represents the number of nodes.
The purpose of all this analysis is to find the Time and Space complexity of the particular tree and to find the cost of a particular operation on it.
### Internal vs External nodes
There is a relationship between internal and external nodes in a strict binary tree.
$\text{External nodes} = (m-1)*\text{Internal nodes} + 1$
## Representation of Binary Trees
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
### 1. Array representation
We can fill the array with the elements of the tree level by level like this:
If we observe, there is a relation of indices bwtween left and right child and their parent node.
| Element | Index | Left child | Right child |
| ------- | ----- | ---------- | ----------- |
| A | 1 | 2 | 3 |
| B | 2 | 4 | 5 |
| A | 3 | 6 | 7 |
There the relationships are
$$
\begin{aligned}
\text{Element} & = i \\
\text{Left} & = 2*i \\
\text{Right} & = 2*i+1 \\
\text{Parent} & = \left\lfloor{\frac{i}{2}}\right\rfloor
\end{aligned}
$$
The parent can be found from left and right child by taking floor(index/2).
### 2. Linked representation
We can represent tree using linked representation where every node is like a node of a Linked List and contains two pointer for left and right child and a field for storing the data.
```graphviz
digraph D
{
rankdir=LR
node[shape=record]
layout=neato
A[label="{left|data|right}",pos="0,0!"]
T[label="Node",color=invis,pos="0,0.5!"]
T->A [color=invis]
}
```
It can be defined in C/C++ using the struct
```cpp
struct Node
{
struct Node* left;
int data;
struct Node* right;
}
```
Therefore, the logical diagram in the memory looks likes this
```graphviz
digraph D
{
node[shape=record]
edge[dir=none]
A[label="|A|"]
B[label="|B|"]
C[label="|C|"]
D[label="/|D|/"]
E[label="/|E|/"]
F[label="/|F|/"]
G[label="/|G|/"]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
## Full vs Complete Binary Tree
**Full Binary Tree:** If there is tree of height `h`, then there should be maximum number of nodes present in the tree for the height `h`.
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
```graphviz
digraph D2
{
rankdir=LR
node[shape=record]
layout=neato
A[label="{A|B|C|D|E|F|G}",pos="0,0!"]
}
```
**Complete Binary Tree:** If a binary tree represented in an array, then there should not be any blank spaces in between the elements. This the condition for a complete binary tree.
```graphviz
digraph D1
{
node[shape=circle]
edge[dir=none]
G[label="",color=invis]
A -> {B, C}
B -> {D, E}
C -> F
}
```
```graphviz
digraph D
{
rankdir=LR
node[shape=record]
layout=neato
A[label="{A|B|C|D|E|F|}",pos="0,0!"]
}
```
**Definition:** A complete binary tree of heigth `h`, will be a full binary tree of `h-1` height and in the last level the elements will be filled from left to right without skipping any position.
Complete binary tree is useful when we are storing the trees in an array and we do not want any blank spaces in the array.
**All Full Binary Trees are Complete Binary Trees but all Complete Binary Trees need not be Full Binary Trees.**
## Tree Traversals
Traversing is visiting all the nodes. For linear structures we can traverse it in forward and bckwards direction. For non-linear structures like tree, there are different methods to traverse it,such as:
1. Preorder: visit(node), Preorder(left), Preorder(right)
2. Indorder: Inorder(left), visit(node), Indorder(right)
3. Postorder: Postroder(left), Postorder(right), visit(nodes)
4. Level order: Level by Level
Examples:
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
A -> {B, C}
}
```
Preorder: A, B, C
Inorder: B, A, C
Postorder: B, C, A
Level order: A, B, C
```graphviz
digraph D
{
node[shape=circle]
edge[dir=none]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
We can find the traversals of bigger trees by breaking the tree into smaller trees.
Postorder: A,(B,D,E),(C,F,G)
Inorder: (D,B,E),A,(F,C,G)
Postorder: (D,E,B),(F,G,C),A
Here we first do the traversal of the larger tree and put brackets for the left and right child. Then we can do the traversal of the smaller tree and find the result.
### Program
```graphviz
digraph D
{
node[shape=record]
edge[dir=none]
A[label="|8|"]
B[label="|3|"]
C[label="|5|"]
D[label="/|4|/"]
E[label="/|9|/"]
F[label="/|7|/"]
G[label="/|2|/"]
A -> {B, C}
B -> {D, E}
C -> {F, G}
}
```
#### i. Preorder
```cpp
void Preorder(Node* root)
{
if (root == NULL)
return;
cout << root->data << " ";
Preorder(root->left);
Preorder(root->right);
}
```
##### Tracing
```graphviz
digraph D
{
node[shape=rect, color=invis]
edge[dir=none]
"Preorder(8)" -> {8, "Preorder(3)", "Preorder(5)"}
"Preorder(3)" -> {3, "Preorder(4)", "Preorder(9)"}
"Preorder(4)" -> {4, "P1", "P2"}
"P1" -> "X1"
"P2" -> "X2"
"Preorder(9)" -> {9, "P3", "P4"}
"P3" -> "X3"
"P4" -> "X4"
"Preorder(5)" -> {5, "Preorder(7)", "Preorder(2)"}
"Preorder(7)" -> {7, "P5", "P6"}
"P5" -> "X5"
"P6" -> "X6"
"Preorder(2)" -> {2, "P7", "P8"}
"P7" -> "X7"
"P8" -> "X8"
"P1"[label="Preorder(0)"]
"P2"[label="Preorder(0)"]
"P3"[label="Preorder(0)"]
"P4"[label="Preorder(0)"]
"P5"[label="Preorder(0)"]
"P6"[label="Preorder(0)"]
"P7"[label="Preorder(0)"]
"P8"[label="Preorder(0)"]
"X1"[label="X"]
"X2"[label="X"]
"X3"[label="X"]
"X4"[label="X"]
"X5"[label="X"]
"X6"[label="X"]
"X7"[label="X"]
"X8"[label="X"]
}
```
**Output: 8 3 4 9 5 7 2**
#### ii. Inorder
```cpp
void Inorder(Node* root)
{
if (root == NULL)
return;
Inorder(root->left);
cout << root->data << " ";
Inorder(root->right);
}
```
#### iii. Postorder
```cpp
void Postorder(Node* root)
{
if (root == NULL)
return;
Postorder(root->left);
Postorder(root->right);
cout << root->data << " ";
}
```
## Creating a Binary Tree
We can create a binary tree level by level using a queue. First we have to create the root node and set left, right child to NULL and set the appropriate data in the node. Then we enqueue the address of root in the queue. After that we ask the user to input left and right child using the same procedure above and push there adresses to the queue.
```c
void Treecreate()
{
struct Node *p, *t;
int x;
struct Queue q;
create(&q, 100);
printf("Enter root value ");
scanf("%d", &x);
root = (struct Node*)malloc(sizeof(struct Node));
root->data = x;
root->lchild = root->rchild = NULL;
enqueue(&q, root);
while (!isEmpty(q))
{
p = dequeue(&q);
printf("Enter left child of %d ", p->data);
scanf("%d", &x);
if (x != -1)
{
t = (struct Node*)malloc(sizeof(struct Node));
t->data = x;
t->left = t->right = NULL;
p->left = t;
enqueue(&q, t);
}
printf("eneter right child of %d ", p->data);
scanf("%d", &x);
if (x != -1)
{
t = (struct Node*)malloc(sizeof(struct Node));
t->data = x;
t->left = t->right = NULL;
p->right = t;
enqueue(&q, t);
}
}
}
```
We use `-1` when we don't want any node to be inserted.
## Generating Trees from Traversals
Trees can be generated from traversals if both preorder and inorder are given or postorder and inorder are given. Tree cannot be generated if **only** preorder or postorder are given.
## Counting the number of nodes
```c
int count(struct Node* p)
{
int x, y;
if (p)
{
x = count(p->left);
y = count(p->right);
return x + y + 1;
}
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
