# Threaded Binary Tree | Data Structure

In this article, we will learn about the **introduction of threaded binary tree**, **types of threaded binary tree** and the **advantages, disadvantages of threaded binary tree** in data structure.

Submitted by Prerana Jain, on July 25, 2018

## Threaded Binary Tree

A binary tree can be represented by using array representation or linked list representation. When a binary tree is represented using linked list representation. If any node is not having a child we use a NULL pointer. These special pointers are threaded and the binary tree having such pointers is called a threaded binary tree. Thread in a binary tree is represented by a dotted line. In linked list representation of a binary tree, they are a number of a NULL pointer than actual pointers. This NULL pointer does not play any role except indicating there is no child. The **threaded binary tree** is proposed by A.J Perlis and C Thornton. There are three ways to thread a binary tree.

- In the in order traversal When The right NULL pointer of each leaf node can be replaced by a thread to the successor of that node then it is called a right thread, and the resultant tree called a right threaded tree or right threaded binary tree.
- When The left NULL pointer of each node can be replaced by a thread to the predecessor of that node under in order traversal it is called left thread and the resultant tree will call a left threaded tree.
- In the in order traversal, the left and the right NULL pointer can be used to point to predecessor and successor of that node respectively. then the resultant tree is called a fully threaded tree.

In the threaded binary tree when there is only one thread is used then it is called as one way threaded tree and when both the threads are used then it is called the two way threaded tree. The pointer point to the root node when If there is no in-order predecessor or in-order successor.

**Consider the following binary tree:**

The in-order traversal of a given tree is **D B H E A F C G**. Right threaded binary tree for a given tree is shown below:

### Advantages of Thread Binary Tree

Non-recursive pre-order, in-order and post-order traversal can be implemented without a stack.

### Disadvantages of Thread Binary Tree

- Insertion and deletion operation becomes more difficult.
- Tree traversal algorithm becomes difficult.
- Memory required to store a node increases. Each node has to store the information whether the links is normal links or threaded links.

### Types of Threaded of Binary Tree

There are three types of Threaded Binary Tree,

**1) Right Threaded Binary Tree**

Right threaded binary tree for a given tree is shown:

**2) Left Threaded Binary Tree**

Left threaded binary tree for a given tree is shown:

**3) Fully Threaded Binary Tree**

Fully threaded binary tree for a given tree is shown:

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions