Home Data Structures Tree Data Structure Tutorial and application

Tree Data Structure Tutorial and application

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:

  1. Each tree has a root node.
  2. If a tree has n nodes, then it will have (n-1) edges only.
  3. A node with degree 0(or no children) is called a leaf node.
  4. 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.
  5. A path is the length of edges between source node to other destination nodes.
  6. 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.
  7. The level of a tree is always height + 1.
  8. 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. 

 

Example

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.

Ternary (3-ary) Tree
Ternary Tree


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
  1. Store hierarchical data, like folder structure, organization structure, XML/HTML data
  2. Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
  3. Trie Used to implement dictionaries with prefix lookup.
  4. Spanning Trees and shortest-path trees are used in routers and bridges respectively in computer networks
  5. B-Tree and B+ Tree They are used to implement indexing in databases.
  6. Binary Search Tree is a tree that allows fast search, insert, delete on sorted data. It also allows finding the closest item
  7. Representing sorted lists of data.
  8. Creating Binay & Binary Search Tree.

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here