Introduction to Tree

Intro:

- What is a tree?

- Tree is a connected undirected graph with no cycle. The tree can be rooted or non-rooted.

See, here the First one is a tree because all nodes are connected and at the same time it has no cycle but on the other hand the second one is not a tree, where all nodes are connected, undirected but it has a cycle.

So, Some basic properties of a tree:

1. One Connected Component.

2. No Cycle.

3. If there are N vertices, then there will be exactly N-1 Edges.

4. Every two vertices are connected by exactly one unique path.

5. Every edge is a bridge, because if we remove any of these edges the connected components will be increased.

6. After removing edges, if all connected components are still trees, then we called it "Forest".

7. Leaf is vertices that are degree one, which means it has only one edges incident to it.

The tree can be rooted or non-rooted, here we mark node 1 as its root.
Edge is like a bridge or path.
Subtree, Suppose we take a node of a tree is 1 and we consider all nodes given below of node 1, they are subtree of node 1. Here subtree of node 1 => nodes 2,4,5,8.

If a node has no child they are called Leaf, here nodes 8, and 9 are Leaf.

We make level only in the rooted tree. Here if we take 1 indexed, then Level 1 is the only root, then level 2 nodes are 2 and 3, level 3 nodes are 4,5,6 and level 4 nodes are 8,9.  Basically, Level means the distance between two nodes, suppose we take node 1 and node 9, the distance between them is 4, that is (4-1).

Consider the tree that is given on the left side, it has 10 vertices(nodes) and 9 edges.

Ancestor, any element which is connected further up, doesn't matter how many levels are higher. More specially, if we take any node 'U', and we start visiting towards the parent and if we met with any nodes then they all are ancestors of node 'U'. Suppose we take node 8, and we start visiting towards parent(1) then we met with nodes 5,2,1. Yes, nodes 5,2, and including parent 1 is ancestors of node 8.

Descendant, any element which is connected in lower, doesn't matter how many levels are lower. Here, node 3 has 4 descendants that are nodes 6,9,7, and 10. Node 8 has no descendent.