Create a doubly linked list from a Binary tree in Kotlin

by

To create a doubly linked list from a binary tree, we can use a modified depth-first search (DFS) algorithm to traverse the binary tree and create a doubly linked list.

Here are the steps to create a doubly linked list from a binary tree:

  1. Create a new doubly linked list with a head and a tail pointer, both initialized to null.
  2. Traverse the binary tree in-order using DFS. When visiting a node, do the following:
    • Create a new node for the doubly linked list.
    • Set the value of the new node to the value of the current node in the binary tree.
    • Add the new node to the end of the doubly linked list using the tail pointer.
    • Set the previous pointer of the new node to the current tail pointer.
    • Set the next pointer of the current tail pointer to the new node.
    • Update the tail pointer to point to the new node.
  3. Once the binary tree has been fully traversed, return the head pointer of the doubly linked list.
      1
     / \
    2   3
   / \    \
  4   5    6

Traversing the binary tree in-order using DFS yields the sequence 4, 2, 5, 1, 3, 6. As we traverse the binary tree, we create new nodes in the doubly linked list and add them to the end of the list. The resulting doubly linked list looks like this:

Null<- | 4 | <=> | 2 | <=> | 5 | <=> | 1 | <=> | 3 | <=> | 6 | -> Null

Here’s an example of a binary tree and the resulting doubly linked list:

Kotlin
class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class DoublyLinkedListNode(var value: Int, var prev: DoublyLinkedListNode? = null, var next: DoublyLinkedListNode? = null)
fun binaryTreeToDoublyLinkedList(root: TreeNode?): DoublyLinkedListNode? {
    if (root == null) {
        return null
    }   
    var head: DoublyLinkedListNode? = null
    var tail: DoublyLinkedListNode? = null
    fun dfs(node: TreeNode) {
        val listNode = DoublyLinkedListNode(node.value)
        if (head == null) {
            head = listNode
        }
        if (tail != null) {
            tail!!.next = listNode
            listNode.prev = tail
        }
        tail = listNode   
        node.left?.let { dfs(it) }
        node.right?.let { dfs(it) }
    }
    dfs(root)  
    return head
}
fun main() {
    // Create a binary tree
    val root = TreeNode(1,
        TreeNode(2,
            TreeNode(4),
            TreeNode(5)
        ),
        TreeNode(3,
            null,
            TreeNode(6)
        )
    )   
    // Convert the binary tree to a doubly linked list
    val head = binaryTreeToDoublyLinkedList(root)   
    // Print the resulting doubly linked list
    var current: DoublyLinkedListNode? = head
    while (current != null) {
        print("${current.value} ")
        current = current.next
    }
    println()
}
  1. The function takes a single argument, root, which is a TreeNode representing the root of the binary tree to be converted to a doubly linked list.
  2. The function begins by checking if the root is null. If it is, then the function returns null.
  3. If the root is not null, the function initializes two variables, head and tail, to null. These variables will be used to build the doubly linked list as we traverse the binary tree.
  4. The function defines a nested function, dfs, which performs a depth-first search of the binary tree and creates a new DoublyLinkedListNode for each node in the tree. The function takes a single argument, node, which is a TreeNode representing the current node in the binary tree.
  5. Inside the dfs function, a new DoublyLinkedListNode is created with the same value as the current TreeNode. This new node is added to the end of the doubly linked list using the tail variable. If tail is not null, the next pointer of the current tail is set to the new node, and the prev pointer of the new node is set to the current tail. The tail variable is then updated to point to the new node.
  6. The dfs function then recursively calls itself on the left and right children of the current node, if they exist.
  7. After the dfs function has finished traversing the binary tree, it returns the head variable, which is the head of the resulting doubly linked list.
  8. Finally, in the main function, a binary tree is created and passed to the binaryTreeToDoublyLinkedList function. The resulting doubly linked list is then printed to the console by iterating over each node in the list and printing its value.

The time complexity of the binaryTreeToDoublyLinkedList function is O(n), where n is the number of nodes in the binary tree. This is because the function performs a depth-first traversal of the entire tree, visiting each node once.

The space complexity of the function is also O(n), where n is the number of nodes in the binary tree. This is because the function creates a new DoublyLinkedListNode for each node in the binary tree, and each node has a constant amount of space overhead (i.e., the value of the node and pointers to the previous and next nodes). In the worst case, when the binary tree is a linear chain (i.e., each node has only one child), the doubly linked list will also be a linear chain with n nodes, so the space complexity is O(n).

Leave a Comment