Trees are the non- linear data structures that represent a hierarchical relationship among various elements. Tree is a collection of nodes which are connected to each other.
Look at the basic tree structure in the figure below:
Untill now we deal with linear data structures like Array, Linked List etc. But Trees are non-linear data structure. Why ??
See in Array, Linked List, Stack, Queues etc you see a logical sequence which have a previous and a next element But as Trees are non-linear data structure, here the elements are arranged in a hierarchical way logically just like an inverted tree.
See full video of Introduction to Tree Data Structure
Important Points about Trees
Fig.: 1
- Trees are the collection of Nodes which are connected to each other
- Each node can point to none, one or multiple nodes which in turn points to several other nodes.
- Each node has exactly one parent only except the root node.
- Nodes that don’t have child means which do not point to any node are called leaf Node or Terminal Node( See Fig. 1)
- Nodes that are having same parent are called Siblings.
- There is a Single unique path from Root node to any particular Node.
Edge
The path or link of the Parent Node to its Child Node is called the Edge or Branch ( See Fig. 1)
If a tree have 'n' Nodes, then it have 'n-1' edges.
Subtree
Subtree is the Portion of the whole tree, that can be seen as a tree. All leaf nodes are also subtrees but all Subtrees are not Leaf Nodes.
Degree of Node
Number of subtrees of a node is called Degree of Node.
Internal Node
All the nodes Between Root and the leaf nodes are known as Internal Nodes
Level of a Node
It is the distance of any Node from the root node in terms of no. of nodes. [Root Node is at Level 0]
Depth of Tree
It is the maximum number of levels of a tree. It is also called weight of tree.
Depth of Tree = Max levels of tree + 1.