'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jan 1, 2024

Introduction to Trees

Author Teesha Goyal
1 upvote
gp-icon
Discrete Mathematics
Free guided path
3 chapters
31+ problems
gp-badge
Earn badges and level up

Introduction

A tree is a Data Structure in which the elements are stored in hierarchical order. A tree is also defined as an acyclic graph or a graph with no cycle. A tree is made up of nodes and edges, where nodes represent the values at that point and edges represent some relation or connection between the nodes. 

Fig 1. Tree Data structure

Properties of Tree 

  • Root Node: It is a specially designed data item in a tree. It is the first in the hierarchical arrangement of data items. The number of incoming edges to this node is zero.
     
  • Node: Each data item in a tree is called a node. It is the basic structure of a tree. It specifies the data information and links to other data items. 
     
  • Degree of node: It is defined as the number of children of a node.
     
  • Degree of Tree: The degree of a tree is the maximum degree of any of its nodes.
     
  • Terminal Nodes/Leaf nodes: A node with the degree of zero or a node that has no child is called a terminal node or a leaf node. 
     
  • Non-Terminal Node: Any node (except the root node) whose degree is not 0 or any node that has both in-degree and out-degree.
     
  • Siblings: The children node of a given parent node are called siblings.
     
  • Level: The root node is on level 0, the children of the root node are at level 1, and the children of level 1 node are at level 2 and so on.
     
  • Edge: The connections between the nodes are represented with the help of edges. If a tree has n nodes, then there are n-1 edges.
     
  • Height/Depth: It is defined as the number of levels in a tree.
     
  • Forest: It is a collection of more than one tree that is not connected.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Happy Coding!

Next article
Traversing Binary Trees
Guided path
Free
gridgp-icon
Discrete Mathematics
3 chapters
31+ Problems
gp-badge
Earn badges and level up
Live masterclass