A tree is a Data Structure composed of nodes, where each node is a data structure consisting of value, together with a list of references to the children
Properties of the tree data structure:
- Each tree has a root node.
- If a tree has n nodes, then it will have (n-1) edges only.
- A node with degree 0(or no children) is called a leaf node.
- A m-ary tree can have at most m children ( maximum degree m). Ex: 2-ary or Binary Tree can have at most 2 children only.
- A path is the length of edges between source node to other destination nodes.
- The height of a tree represents the number of edges on the longest path between the root node and a leaf. The height of leaf nodes is always 0.
- The level of a tree is always height + 1.
- Max no. of leaf nodes L= n(m-1) + 1 . Here m represents m-ary tree(m=2 for a binary tree, m=3 for ternary tree and so on), and n is the number of internal nodes with degree m.
Following is a Ternary (3-ary) Tree
The maximum degree of a node is 3.(Node 7 has max degree 3).
The height of the tree is 3.(Following are the path with maximum path length so will count them towards height 2->7->6->5 or 2->7->6->11 or 2->5->9->1).
2(marked red) is the root node with height 3. 2, 10, 5, 11, 4 are the leaf nodes with height 0.
Important terminologies related to Tree Data Structure
Node: A node is a structure that may contain a value.
Root: The top node in a tree.
Child: A node directly connected to another node when moving away from the root, an immediate descendant.
Parent: The converse notion of a child, an immediate ancestor.
Siblings: A group of nodes with the same parent.
Ancestor: A node reachable by repeated proceeding from child to parent.
Leaf node: A node with no children.
Internal node: A node with at least one child.
Degree: For a given node, its number of children. A leaf is necessarily degree zero. The degree of a tree is the degree of its root.
Edge: The connection between one node and another
Sub Tree: A tree T is a tree consisting of a node in T and all of its descendants in T.
Application of Tree Data Structure
- Store hierarchical data, like folder structure, organization structure, XML/HTML data
- Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
- Trie Used to implement dictionaries with prefix lookup.
- Spanning Trees and shortest-path trees are used in routers and bridges respectively in computer networks
- B-Tree and B+ Tree They are used to implement indexing in databases.
- Binary Search Tree is a tree that allows fast search, insert, delete on sorted data. It also allows finding the closest item
- Representing sorted lists of data.
- Creating Binay & Binary Search Tree.