Select Page

# Converting a Binary Tree to a Doubly Linked List in Java ## Introduction

In this tutorial, we will learn how to convert a given binary tree to a doubly linked list using Java programming language. Binary trees are hierarchical data structures where each node can have at most two children, referred to as the left child and the right child. On the other hand, a doubly linked list is a linear data structure in which each node has a reference to both its previous and next node.

## Algorithm

To convert a binary tree to a doubly linked list, we can use the following algorithm:

1. Start by creating an empty doubly linked list.
2. Traverse the binary tree using any tree traversal algorithm.
3. For each node encountered during the traversal, perform the following steps:
1. Set the left pointer of the current node to the last node in the doubly linked list.
2. If the last node is not null, set its right pointer to the current node.
3. Set the current node as the last node in the doubly linked list.
4. Set the right pointer of the current node to the next node in the traversal (if any).
4. After traversing the entire binary tree, the doubly linked list will be formed.

## Implementation

Here is the Java implementation of the algorithm:

``````class Node {
int data;
Node left, right;

public Node(int item) {
data = item;
left = right = null;
}
}

Node root;
Node lastNode;

if (node == null)
return;

if (lastNode == null) {
root = node;
} else {
node.left = lastNode;
lastNode.right = node;
}
lastNode = node;

The above implementation uses a class named `Node` to represent each node in the binary tree. The `convertToDoublyLinkedList` method is responsible for converting the binary tree to a doubly linked list. It uses a recursive approach to traverse the binary tree and performs the necessary pointer manipulations to form the doubly linked list.