A tree is a non-linear data structure. It means you cannot access an element of tree in a straightforward manner.In this lesson, you learn about tree basics. This will serve as a foundation for future topics on trees. You can start learn about other topics if familiar with basics.

### Informal definition of Tree

A tree is a set of one or more nodes with a special node called a **Root node**. Every none points to a left node and a right node. Sometimes left, right or both are missing and a node points to nothing.

Every node is part of some smaller set of nodes called a **Sub-tree**. Each sub-tree has more sub-trees.

### Tree basics – Directed vs Undirected Tree

In an undirected tree, the edge between two nodes has no direction associated with it. However, a directed tree has some important properties

- The directed tree is
**acyclic**means there is loop between the nodes. - The directed tree is
**digraph**means it is like a graph with direction. Each node has associated edges. If the node pointed by some other node, it is called an**In-degree**and if the node is pointing to some other node, its called an**Out-degree.** - Root node has in-degree 0 and all other nodes have in-degree of 1.
- The minimum number of node allowed in a directed tree is 1. So, an isolated node is a directed tree.

### Leaf Nodes

**Leaf node or Terminal node.**

In the above figure, 5 , 6 , 7, 8, 9 are leaf nodes.

### Branch Nodes

In the above figure, 2, 3 and 4 are branch nodes.

### Level of a Tree

**1 –> 4 –> 8**

### Tree basics – Ordered Tree

**Ordered tree.**

In the above figure the Tree A and Tree B are same tree, but ordered differently.

### Node degree

The node 2 from tree B has a degree of 2 because node 4 and node 3 are its children.

### The Concept of Forest

**Forest.**

**Forest A ={ (2,3,4),( 5,6)} Forest B = {(5,6),(2,3,4)}**

### Descendant & Children of a Node

**Descendant**of a node N.

**Child**of node N and the node N is a

**Parent**of child node S.

### Bibliography

E.Balaguruswamy. 2013. *Data Structures Using C.* McGraw Hill Education.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. *Introduction to Algorithms.* MIT Press.