×

What is a Threaded Binary Tree?

When we consider those binary trees that are interlinked with each other, we do come across the fact that the fields present in there do consist of NULL values that ultimately lead to the damage and wastage of the storage space that we use for the tree. If we have a binary tree that comprises n number of nodes, then the n+1 link fields would definitely have the NULL values.

In order to save and manage the wastage of this storage space, a new convention was introduced by two people named Perlis and Thornton. In this particular method, the links which were previously filled with NULL are significantly replaced by threads. So, the binary trees that contains threads as a replacement, those binary trees are termed threaded binary trees. Each and every node in a threaded binary tree either contain a link to their child node or thread to various other nodes present in the tree.

Types of threaded binary tree

There are majorly two types of the threaded binary trees. They are given below: -

  • One-way threaded binary tree
  • Two-way threaded binary tree

Now, we will explain each of these trees one by one in the given section.

One-way threaded binary tree

In this type of threaded binary tree, the thread usually occurs either at the left or right link of the field of a given node. If, for example, say the link pops up at the right link of the field, then it will ultimately lead and point to the next adjacent node that will appear and perform the inorder traversal operation on the tree.

Such types of trees are vividly known as the Right threaded binary trees. Whereas on the other hand, if suppose the link pops out at the left link of a given node, then it will ultimately lead and point to the next adjacent node that will appear and perform the inorder predecessor operation on the tree. Such types of trees are known as the left threaded binary trees. In such kind of threaded binary trees, the right link of the last node and the left link of the first node generally occupies a NULL value.

WHAT IS A THREADED BINARY TREE

A question arises here how do we distinguish links from threads so the answer to the same question is that threads are generally denoted by dotted lines and are pretty visible to human eyes as well.

WHAT IS A THREADED BINARY TREE

The above picture depicts that the inorder traversal and exploration of the threaded binary tree turns out to be vivid with the nodes D, B, E, A, C, and F. When this given tree is represented as the right threaded binary tree, the right link present on the tree placed on the leaf node D that also contains NULL value is generally exchanged with a thread which is represented by a dotted line. This node directly heads out and points to node B, which is the successor of node D. Likewise, in the same way, all the other trees are allotted threads.

Two-way threaded binary tree

In this type of threaded binary tree, the right link of the node which contains the NULL value is generally changed by the thread that usually enacts and points out to the nodes that are inorder successor and the left link of the node which also contains the NULL value is generally replaced by the thread. It points out the nodes that are present in the inorder predecessor.

WHAT IS A THREADED BINARY TREE
WHAT IS A THREADED BINARY TREE

Take a look at the above picture that shows us the inorder traversal of the threaded binary tree having the vertices D, B, E, G, A, C, and F. If we look at this threaded binary tree, the node that is named E that contains the value NULL is generally interchanged by a simple thread which is a dotted line to its inorder former which node B.

Likewise, the node G that we see in the above picture contains left and right field links that already contain NULL values that are also exchanged by threads which are represented by dotted lines. This is done in such a way that the right link field generally points inorder successor, and in the same manner the left link heads out to the inorder predecessor. In the same manner, all the nodes that are present in the field are allotted threads.


Related Topics

Berkley’s Algorithm

Berkley’s Algorithm is mainly used in clock synchronization system. It is used in distributed systems. To implement this algorithm, we have to think that the network has no accurate time...

4 minutes read.

Sparse Matrix in Data Structure

Sparse Matrix The sparse matrix is a two-dimensional data object which is made by m rows and n columns, so we can say the number of data values in sparse matrix...

6 minutes read.

Advantages and Disadvantages of Linked List

Advantages of Linked List The linked list is a dynamic data structure.You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at...

3 minutes read.

Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List This article will explain how we can count the occurrences of a particular element in a list. Here,...

3 minutes read.

What are Forest Trees in Data Structure

Data structure A data model manages and optimizes computer resources, and a database stores and manages data. It's one of many uses for data structures to hold data. Data structures come...

5 minutes read.

Vertical Order Traversal of Binary Tree

Implementation #include <iostream> #include <vector> #include <map> using namespace std; // representing the primary model of a binary tree node. struct _nod { int ky; _nod *Lft, *Rt; }; // establishing a new function representing the new binary tree node. struct _nod*...

5 minutes read.

Linear vs Circular Queue: Data Structure

Difference Between Linear and Circular Queue What is Linear Queue? A linear queue is linear data structure which works on first in first out principle. We can say a linear queue is...

3 minutes read.

Bitonical Sort

Arranging an unordered collecttion of things into asignificant order. •Comparision Based Model: Bubble Sort, Selection Sort -->Non-Comparison Based. Model: Bucket Sort or on the other hand a Count Sort Bitonic Sort: Bitonic sort Algorithm was made...

5 minutes read.

Given a Binary Tree, Check if it's balanced

Implementation /*Creating a C++ program that will help us identify whether the given tree is height-balanced or not.  */ #include <bits/stdc++.h> using namespace std; /* A particular binary tree node consists of data with some...

4 minutes read.

Compare Balanced Binary Tree and Complete Binary Tree

Complete and balanced binary trees are important and general topics in the concept – Tree data structure. Before discussing the complete and balanced binary tree, we need to have an...

8 minutes read.

Perfect Binary Tree

Complete binary trees are an important and general topic in the concept – of tree data structures. Before discussing a complete binary tree, we need to know the concept of...

4 minutes read.

Convert Binary Tree into a Threaded Binary Tree

Implementation /*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */ #include <bits/stdc++.h> using namespace std; /*Creating the structure of a node...

11 minutes read.

Arrange consonants and vowels nodes in a linked list

Arrange consonants and vowels nodes in a linked list In this problem, we have given a singly linked list. Here we will arrange the consonants and vowels nodes of the list...

2 minutes read.

Delete the Middle element of the Linked List in C

Delete the Middle element of the Linked List in C This article has given a singly linked list and will delete the middle element of the given linked list. Example:  The given...

3 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Structure and Union Data Structure

The array is used for the same type of data, but if we want to store a mixed type of data in a group, then the array cannot be used. The Structure...

4 minutes read.

Tim Sort

Tim Sort is a mixture stable arranging calculation that exploits normal examples in information, and uses a mix of an improved Merge sort and Binary Insertion sort alongside an interior...

6 minutes read.

Complete Binary tree

In this article, we will discuss the complete binary tree. But before start discussing the complete binary tree, we should first see a brief description of a binary tree. What is...

7 minutes read.

Heap Sort in Data Structure

Heap Sort A heap is a tree-based data structure that has specific properties. Heap is always a complete binary tree (CBT). That is, all the nodes of the tree are completely filled.If...

6 minutes read.

Strictly binary tree in Data Structures?

What is a strictly Binary Tree in Data Structures? There are various kinds of binary trees that we know exist in data structures, and they all have their purposes. In this...

4 minutes read.