What is a tree data structure?

A tree data structure is a non–linear structure that stores data hierarchically. It can be defined as a group of objects, called nodes. The nodes are linked with edges. Trees begin with a root node which leads to children nodes. The last children nodes (endpoints) are called leaf nodes, and they do not have children nodes.

Terminologies used in tree data structures

Before studying trees, it is essential to learn the common terminologies used in the tree data structure.

• Parent - If a node has any branch (sub-node), that node is called the parent of the sub-node.
• Child - A child node is the descendant of any node.
• Sibling - Children with the same parent node are siblings.
• Root - Root is the topmost node in a tree. Every tree begins with the root node, and a tree can have at most one root. A root node does not have any parent.
• Leaf/ External node - It is the bottom-most node of the tree and contains no child.
• Internal node - Nodes that have at least one child are internal nodes.
• Height of node - The node height is the number of edges from the node to the leaf of that node.
• Height of tree - It is the height of the root node. It is the number of edges from the root node to the leaf node.
• Depth of node - It is the number of edges from the root node to the current node.

Types of trees

The common types of trees in data structures are discussed below.

General trees

General trees have no restrictions on the number of nodes. They can have 0 or more nodes. The topmost node in such trees is the root node, and the children of the parent node are subtrees. These types of trees are used to store hierarchical information like folder structures.

The figure below shows a general tree, where the root node is 2.

Binary trees

In binary trees, each node can have at most two children, and the children are called the right child and the left child. That indicates that binary trees can have 0, 1, or 2 nodes. Compilers use binary trees to create syntax trees.

Below is the basic representation of binary trees. Here, the root node is 2, and each tree node has 2 children at most.

Binary search trees

A binary search tree is a subtype of a binary tree that stores numbers in an organized way. In a binary search tree, each node of the left subtree should have a value lesser than or equal to the parent node, whereas the nodes in the right subtree should have a value greater than or equal to the parent node. Each node in these trees can have a maximum of two nodes.

Consider the following binary search tree. In this tree, the root node is 8, and all the nodes in the left sub-tree have a value lesser than the root node. The nodes in the right subtree have a value greater than the parent node.

Adelson-Velsky-Landis (AVL) trees

An AVL tree is a type of binary tree where a balancing factor is assigned to each node. The balancing factor is the difference between the left and right subtree heights. The balancing factor can be 0, 1, and -1.

The AVL trees are height-balanced, and the height of the child node can be at most 1. Whenever a new node is added to the tree, it is rotated to make sure the tree remains balanced.

The figure below represents an AVL tree where the balancing factors are denoted in green color.

Red black trees

Red-black trees are also self-balancing trees, but they contain nodes painted red or black. The painted nodes ensure that the tree remains balanced after insertion or deletion operations. When a node is added to the tree, the nodes are rotated, and if required, they are painted to ensure the tree is balanced. If a node is red, its child nodes are black. The root and leaves are always black.

The image below represents a red-black tree. Here, the root node 13 is black and therefore, its children are red. The same applies to the other nodes.

Splay trees

A splay tree is a type of binary search tree that adjusts the most recently accessed node such that it can be accessed quickly. It performs the rotational operation to arrange the recently accessed node as the root node of the tree.

Consider the following splay tree. Here, when node x is searched, the tree will rotate and make node x the root node.

B-tree

B-tree is a self-balancing tree that generalizes the binary search tree. Nodes of B-trees can have more than one value and more than two children. All the leaf nodes in the B-tree should be at the same level. B-trees are mostly used in storage systems that read/ write large amounts of data.

The figure below represents a B-tree, where the root node has multiple key-values, and each leaf node is at the same level.

Uses of trees

Applications of trees are as follows:

• In file systems for storing data on hard drives.
• In priority queues.
• To implement sorting algorithms.
• To build syntax trees for computer languages.
• To build parse trees for human languages.
• To represent sorted lists of data.
• To store data in routing tables in routers.

Context and Applications

Trees and types of trees in the data structure subject is studied by students studying undergraduate and postgraduate courses like:

• Bachelor of Science in Computer Science
• Master of Science in Computer Science
• Bachelor of Science in information technology
• Master of Science in information technology

Practice Problems

Q1) Which of the following is a type of tree?

1. Binary Search tree
2. Search segment tree
3. Floating-point tree
4. Object-oriented tree

Answer: Option a

Explanation: Binary search tree is a type of tree data structure.

Q2) Which type of trees have black and red color painted nodes?

1. T-trees
2. N-ary tree
3. Abstract data types (ADTs)
4. Red-black trees 

Answer: Option d

Explanation: Red-black trees are self-balancing trees having red and black colored nodes.

Q3) How many nodes can each node in the binary tree have at the most?

1. Structure type
2. Twenty
3. Two
4. Five

Answer: Option c

Explanation: Each node in the binary trees can have at most two nodes as its child nodes.

Q4) Which of the following value can be assigned as the balancing factor in an AVL tree?

1. Zero
2. Five
3. Three
4. Ten

Answer: Option a

Explanation: The balancing factor in AVL can have values 0, 1, and -1 only.

Q5) What is the topmost node in a tree called?

1. Root
2. Content
3. Multi-dimensional
4. Breadth-first node

Answer: Option a

Explanation: The topmost node in a tree is the root node.

Common Mistakes

B-trees and binary trees are two different tree data structures. So, students should never consider binary trees as B-trees, and these terms should not be used interchangeably.

Related Concepts

• Arrays
• LinkedLists
• Stack
• Tree traversal (pre-order, post-order traversal)