Skip to main content

Converting a Binary Tree to a Doubly Linked List | Programming Concept | DSA


When it comes to data structures in computer science, binary trees and linked lists are fundamental concepts that often come into play. In this post, we will explore an intriguing problem: converting a binary tree into a doubly linked list (DLL). This task may seem daunting, but with the right approach, we can achieve it seamlessly. Let's dive into the details!

Understanding the Problem

What is a Binary Tree?

A binary tree is a hierarchical structure in which each node has at most two children referred to as the left child and the right child. This structure is crucial for organizing data hierarchically, facilitating efficient searching, inserting, and deleting operations.

What is a Doubly Linked List?

A doubly linked list (DLL) is a linear data structure consisting of nodes, where each node contains three components: a data field and two pointers. One pointer points to the next node in the sequence (next), while the other points to the previous node (prev). This bidirectional nature of DLLs allows for easy traversal in both directions.

Our goal is to convert a given binary tree into a DLL such that:

  • The left and right pointers of the binary tree nodes are repurposed to act as the previous and next pointers in the DLL.
  • The order of nodes in the DLL reflects the in-order traversal of the binary tree.
  • The head of the DLL is the leftmost node of the binary tree.

Efficient Approach

To convert a binary tree into a DLL, we can use a recursive approach. Here’s how the process works:

  1. In-Order Traversal: The in-order traversal visits nodes in the order of left child, current node, and right child. This order is essential because it aligns with our requirement for the doubly linked list.

  2. Node Manipulation: During the traversal, we need to adjust the pointers of the nodes to link them as a doubly linked list.

Implementation

Below is a C++ implementation of the approach discussed:

class Node {
public:
    int data;
    Node* left;  // used as previous pointer in DLL
    Node* right; // used as next pointer in DLL
   
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void create(Node* root, Node* &head) {
        if (!root) return;

        // Traverse right first
        create(root->right, head);

        // Link current node with the head
        root->right = head; // Set the right pointer (next)
        if (head) {
            head->left = root; // Set the left pointer (previous)
        }
        head = root; // Move head to the current node

        // Traverse left
        create(root->left, head);
    }

    Node* bToDLL(Node* root) {
        Node* head = nullptr;
        create(root, head);
        return head; // Return the head of the doubly linked list
    }
};

 

Explanation of the Code

  1. Node Structure: We define a Node class to represent each node in the binary tree, with data, left, and right pointers.

  2. Recursive Function: The create function recursively processes the binary tree. It first traverses the right subtree, then links the current node to the head of the DLL, and finally traverses the left subtree.

  3. Main Function: The bToDLL function initializes the head pointer to nullptr and starts the conversion process.

Complexity Analysis

  • Time Complexity: The time complexity for this conversion is O(n), where n is the number of nodes in the binary tree. Each node is processed once during the traversal.

  • Space Complexity: The space complexity is O(h), where h is the height of the binary tree, due to the recursion stack. In the worst case, for a skewed tree, this can be O(n).

Converting a binary tree to a doubly linked list is a fascinating problem that showcases the power of recursion and pointer manipulation. By following the in-order traversal and appropriately adjusting node pointers, we can efficiently transform the binary tree structure into a DLL.

This approach not only enhances our understanding of trees and linked lists but also equips us with techniques that can be applied to various other data structure problems. Whether you're preparing for coding interviews or just looking to deepen your understanding of data structures, mastering this conversion process is a valuable skill.

Popular posts from this blog

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...
Read more

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more

Final Prices With a Special Discount in a Shop – LeetCode Solution Explained

When tackling coding problems, it's important to understand the problem thoroughly and work through solutions step-by-step. In this blog, we will explore the LeetCode problem "1475 Final Prices With a Special Discount in a Shop" . We'll walk through the problem statement, approach it with a beginner-friendly brute force solution, and analyze its time and space complexity. Finally, we'll discuss any possible optimizations to improve efficiency. Problem Statement You are given an integer array prices where prices[i] represents the price of the i th item in a shop. There is a special discount rule: If you buy the i th item, you receive a discount equal to prices[j] , where j is the smallest index such that j > i and prices[j] <= prices[i] . If no such j exists, you get no discount for that item. Your task is to return a new array answer , where answer[i] is the final price you pay for the i th item after applying the discount. Examples Example 1: Input: p...
Read more