Tree data structure

What is tree?

A tree is a hierarchical data structure that consists of nodes connected by edges. It is NOT a linear data structure.


Element in a tree


The node at the top of the tree is called the root. There is only one root per tree and one path from the root node to any node.


Any node except the root node has one edge upward to a node called the parent.


The node below a given node connected by its edge downward is called its child node.


Subtree represents the descendants of a node.


Visiting refers to checking the value of a node when control is on the node.


Traversing means passing through nodes in a specific order.


The Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.


The key represents a value of a node based on which a search operation is to be carried out for a node.

Leaf nodes:

Leaf nodes are nodes that are on the bottom of the tree and have no children.

Node Depth:

Node depth is the number of links from the root to the node.

Tree Height:

Tree height is the number of links from its root to the furthest leaf. The tree height is the same as the maximum node depth.

Examples of Tree data structure

The tree data structure is widely used in many areas of computer science. The following are some examples of tree data structure:

Filesystems — files inside folders use a tree data structure.
Post comments — reply to comments – replies to reply use a tree data structure.
Family or Organizational hierarchy can be represented by a tree data structure
The heavyly used XML/HTML parsers use a tree data structure. Apache Xerces, Xalan XSLT parser etc.
PDF is a tree based format. It has a root node followed by a catalog node followed by a pages node which has several child page nodes.
Computer chess games use tree data structure to reach an optimal move.
Producers/consumers often use a balanced tree implementation to store a document in memory.
Social networking app often uses tree data structure to represent/identify more interesting criteria. Example: common friends
Decision Tree based Learning actually forms a formidable area of data mining research.
A common problem in bioinformatics is searching huge databases to find matches for a given query string. Tree can be used for efficient searching.
Quite a few successful (stock) traders use decision trees in their day-to-day trading

Tree Traversal classification

Tree Traversal algorithms can be classified broadly into two categories:

  • Depth-First Search (DFS) Algorithms
  • Breadth-First Search (BFS) Algorithms

Depth-First Search (DFS) Algorithms

Depth-First Search (DFS) Algorithms have three variants:

Preorder Traversal (current-left-right) — Visit the current node before visiting any nodes inside the left or right subtrees.
Inorder Traversal (left-current-right) — Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree.
Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of the left and right subtrees.

Breadth-First Search (BFS) Algorithms

Breadth-First Search (BFS) Algorithm has one variant:

Level Order Traversal — Visit nodes level-by-level and left-to-right fashion at the same level.