Introduction to Trees

Types of Trees

General Tree

A tree with no constraints assigned to it comes under the general tree. It can have any number of nodes. Each node in a general tree can have any number of children. It is the superset of all the other kinds of trees. 

Fig 2. Example of General Tree

Directed Tree

A directed tree is a type of tree where directions are assigned on the edges. The Arrow sign is used to show the directions in a directed tree. The node with 0 in-degree is the root node of the given tree. The nodes with out-degree 0 are called the terminal or leaf nodes,, and the nodes with out-degree one or greater are called internal nodes.

Fig 3. Example of Directed Tree

Rooted Tree

A tree in which one node is present with zero in-degree is called the root node. Other than root nodes are either internal nodes or terminal nodes. The internal node is the node that has one or more children, and the terminal node is a node that has no child. 

Fig 4. Example of Rooted Tree 

Ordered Tree

In an ordered tree, all the nodes are ordered in some manner. It is a specification of a rooted tree in which nodes are in some order.

Fig 5. Example of Ordered Tree

Binary Tree

A binary tree consists of a single item called the root and two disjoint binary trees called the left subtree and right subtree

It is the type of tree in which each node can have 0,1 or 2 children; therefore, the maximum degree of any node is 2.

Fig 6. Example of Binary Tree

Binary Search Tree

It is an advancement in the binary tree which is ordered. In a binary search tree, the data item at the left child is smaller in value than the root node, and the data item at the right child is greater than the root node. In this, the left child and the right child should also be a binary search tree.

Fig 7. Example of Binary Search Tree

Also read - Data Structure MCQ

FAQs

1. What is the difference between a binary search tree and a binary tree?
A binary search tree is a specialization of binary trees in which the left child is smaller than the root node, and the right child is larger than the root node.

2. What is the degree of a node of a tree?
The count of the number of children of a node is defined as the degree of the node. In a binary tree, the maximum degree of a node is 2.

3. What is tree data structure?
A tree is a data structure in which the elements are not arranged in hierarchical order. It is an acyclic graph with nodes and edges.

4. What is a non-linear data structure?
In a Non-linear data structure, the elements are not arranged in a sequential manner. Trees and graphs are examples of non-linear data structures.

5. What is tree traversal?
Tree traversal is the process of visiting each node in a tree exactly once. There are three techniques, namely inorder, preorder, and postorder traversal.

Key Takeaways

In this article, we learned that a tree is a non-linear data structure in which elements are stored in an acyclic graph manner. We also discussed its properties and types. 

Check out this problem - XOR Queries On Tree

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

Happy Coding!