Scribd
Upload
258 views13 pages

Threaded Binary Trees

A threaded binary tree utilizes empty child pointers in a binary search tree to link nodes and allow for efficient inorder traversal without recursion. Each node contains additional "thread" fields that can point either to a child node or to the inorder predecessor or successor. For one-way threading the thread fields point only forward or backward in the inorder sequence, while for two-way threading they can point in either direction, linking all nodes without empty subtrees. This representation of the tree removes recursion and allows linear time traversal.

Uploaded by

Vinu Varghese
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
258 views13 pages

Threaded Binary Trees

A threaded binary tree utilizes empty child pointers in a binary search tree to link nodes and allow for efficient inorder traversal without recursion. Each node contains additional "thread" fields that can point either to a child node or to the inorder predecessor or successor. For one-way threading the thread fields point only forward or backward in the inorder sequence, while for two-way threading they can point in either direction, linking all nodes without empty subtrees. This representation of the tree removes recursion and allows linear time traversal.

Uploaded by

Vinu Varghese
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Threaded Binary Trees

Speeding up traversals
Objectives

In this session, you will learn to


Threaded binary tree
Defining Threaded Binary Trees

• In a binary search tree, there are many nodes that have an


empty left child or empty right child or both.
• You can utilize these fields in such a way so that the empty
left child of a node points to its inorder predecessor and
empty right child of the node points to its inorder successor.
Threaded binary Tree
• One way threading:- A thread will appear in a right field
of a node and will point to the next node in the inorder
traversal.
• Two way threading:- A thread will also appear in the left
field of a node and will point to the preceding node in the
inorder traversal.
Defining Threaded Binary Trees

Consider the following binary search tree.


Most of the nodes in this tree hold a NULL value in their left or right child
fields.
In this case, it would be good if these NULL fields are utilized for some
other useful purpose.
. 65 .

. 40 . . 72 .

30 . 50 . 69 80

60
One Way Threaded Binary Trees
The empty left child field of a node can be used to point to its inorder
predecessor.
Similarly, the empty right child field of a node can be used to point to
its in-order successor.
Such a type of binary tree is known as a one way threaded binary tree.
A field that holds the address of its in-order successor is known as thread.
In-order :- 30 40 50 60 65 69 72 80 . 65 .

. 40 . . 72 .

30 50 . 69 80

60
Two way Threaded Binary Trees

Such a type of binary tree is known as a threaded binary tree.


A field that holds the address of its inorder successor or predecessor is
known as thread.
The empty left child field of a node can be used to point to its inorder predecessor.
Similarly, the empty right child field of a node can be used to point to its inorder
successor. . 65 .
Inorder :- 30 40 50 60 65 69 72 80

. 40 . . 72 .

30 50 . 69 80

60
Node 30 does not have an inorder predecessor because it
is the first node to be traversed in inorder sequence.
Similarly, node 80 does not have an inorder successor.

. 65 .

. 40 . . 72 .

30 50 . 69 80

60
Two way Threaded Binary Trees with header Node

The right child of the header node always points to itself.


Therefore, you take a dummy node called the header node.

Header Node

. 65 .

. 40 . . 72 .

30 50 . 69 80

60
The threaded binary tree is represented as the left child of the header node.

Header Node

. 65 .

. 40 . . 72 .

30 50 . 69 80

60
The left thread of node 30 and the right thread of node 80
point to the header node. Header Node

. 65 .

. 40 . . 72 .

. 30 50 . 69 80 .

60
Representing a Threaded Binary Tree

The structure of a node in a threaded binary tree is a bit different from


that of a normal binary tree.
Unlike a normal binary tree, each node of a threaded binary tree
contains two extra pieces of information, namely left thread and right
thread.
The left and right thread fields of a node can have two values:
1: Indicates a normal link to the child node
0: Indicates a thread pointing to the inorder predecessor or inorder
successor

4631 Information 2389

Left Address of Data Address of Right


Thread Left Child Right Child Thread
In a threaded binary tree, the right thread of a node points to
its inorder ___________, and the left thread points to its
inorder ____________.

Answer:
successor, predecessor

You might also like