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. 



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


Please enter your comment!
Please enter your name here