Covert Binary Tree to Doubly Linked List (Microsoft Interview)

We are converting a binary tree into a DLL, in place also we are using in order traversalto do so.

Read more here – Link

My Code:

class BinaryTree():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

def btToDll(node,head):

    prev = None
    return getbtToDll(node,head,prev)

def getbtToDll(node,head,prev):

    if node is None:
        return
    getbtToDll(node.left,head,prev)

    if prev is None:
        head = node
    else:
        node.left = prev
        prev.right = node
    prev = node

    getbtToDll(node.right,head,prev)


def printList(head):
    if head is None:
        print("NO LL FOUND AT THIS NODE")
    else:
        temp = head
        while(temp):
            print(temp.data)
            temp = temp.right


root = BinaryTree(10)
root.left = BinaryTree(12)
root.right = BinaryTree(15)
root.left.left = BinaryTree(25)
root.left.right = BinaryTree(30)
root.right.left = BinaryTree(36)

head = None
head1 = btToDll(root,head)

printList(head1)

My problem: The head is always None and hence I cannot print the converted list. What is wrong with this code or my logic?

Answer

Your code has many Pitfalls, the main reason why it return none is because from btToDll returns nothing, also it doesn’t change the value of head, which it still None.

Instead of trying to repair your code, I preferred to go in a different Approach all in once.

Basically, I found a trick to get the result:

1. Go down to the most left Node which becomes the HEAD.
2. Check if from the Head You can go Up one, then left- left. or Up One right right and so on. If you can go Left then set the current node as the left bottom node. Do this untill there isn’t any Node. Add the Previous node in the DLL list
3. Caluclate the current node, its previous and the Right node from the Previoys.
4. Go back from the Binary Tree, one reach the Root node (10), repeat the same pattern.

You will see that basically, if in any given Sub-node, there is a left node, then you calculate the entire Triangle, the most important node is always the left and becomes the current node. If left node is not present, then the Parent node becomes the current node, then you need to check whether the parent has a right node not.

I prepared some pictures, is much better to visualize this than explain it.

Take this Binary Tree:

First Step | Go To the most far left node as possible

Second Step | Calculate the First Triange

Note: If the Right bottom Node (30) HAS a left child node, then 30 won’t be added, which is the case of this example, instead it goes to the next step.

Step 3 | Go to the next Triangle step of the Child’s child node##

Step 4 | Now go up to the root node and calculate the left side of BT

Note: See the complete path of this algorithm, again I imagine that as many small triangles that are calculated Separately.

Source Code

NOTE: Is been lengthy, but I did it on the fly, can be improved.

class BinaryTree():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.prev = None
        self.visited = False

    def create_tree(self, show_tree=False):
        """Creating the Tree with a Depth-First Search Algorithm"""
            
        root = self # Set Current Node        
        stack = [root]

        while True:

            if not stack:
                break

            current = stack.pop() # Remove Current From Stack

            if current.right:
                current.right.prev = current
                stack.append(current.right)            
            if current.left:
                current.left.prev = current
                stack.append(current.left)

            if show_tree:
                print(f'{current.data} --> ', end='')


def create_dll(root_head):
    """Algorithm to Conver Binary Tree to Doubly Linked List"""

    doubly_linked_list = []

    # --- Find DLL Head NOTE: Just need to go left from Binary Tree till hit NONE
    head = None
    current = root_head 
    while True:
        if current.left:
            current = current.left
        else:
            head = current       
            break
    
    stack = [head]
    visited = set()

    def add_node(*args, add_dll=None):
        """Helper Function, Add Node to the Visited Set."""
        for item in args:
            visited.add(item)
        if add_dll:
            for node in add_dll:
                doubly_linked_list.append(node)

    # --- Crawls back up, following each Triangle Shape from left Vertices to Right
    while True:

        try:
            current = stack.pop()
        except IndexError:
            pass

        if current in doubly_linked_list:
            break
        
   
        if current.left and current.left not in visited: # NOTE: Goes Down to Next Triangle Shape        
            stack.append(current.left)
            continue
        elif current.prev: # NOTE: Goes Up one Node
            add_node(add_dll=[current])

            # ---------------  Check if we can go to the left.
            if current.prev.right.left and current.prev.right.left not in visited: # NOTE: Goes deeper 
                add_node(current.prev, current.prev.right, add_dll=[current.prev])

                if current.prev.prev: # NOTE: Backtracking
                    stack.append(current.prev.prev)
                stack.append(current.prev.right.left)    
                continue

            # ------------- Here We Handle in case previous Node Has ONLY Right path
            elif current.prev.right.right:  
                if current.prev.right.right.left:  # If has Left Node we go deeper
                    stack.append(current.right.right.left)    
                    continue
                add_node(add_dll=[current.prev.right.right])              
            else:     
                add_node(current.prev, add_dll=[current.prev])

                if current.prev.right: # DOES the Prev node have a Right node?
                    add_node(current.prev.right, add_dll=[current.prev.right])
                
        
                if current.prev.prev and current.prev.prev not in visited: # NOTE: BackTrackin
                    stack.append(current.prev.prev)
        #  -------------- >N OTE: Here Handle The 'Root node' (i.e. 10), only option is to go to right
        elif current.right: 
            add_node(current, add_dll=[current])
            if current.right.left: # Going Deeper
                stack.append(current.right.left)    
                continue
            elif current.right.right:   
                if current.right.right.left:
                    stack.append(current.right.right.left)    
                    continue
                add_node(current.right, current.right.right, add_dll=[current.right, current.right.right])                
            else:    
                add_node(current.right, add_dll=[current.right])  
    
    return doubly_linked_list

    
def show_ddl(ddl):
    """Helper function, used to print the Doubly Linked List"""
    for node in ddl:
        print(f'{node.data} --> ', end='')


# --------->  Creating The Binary Tree >

root = BinaryTree(10)
root.left = BinaryTree(12)
root.right = BinaryTree(15)
root.left.left = BinaryTree(25)
root.left.right = BinaryTree(30)
root.left.right.left = BinaryTree(60)           
root.left.right.right = BinaryTree(77)
root.right.right = BinaryTree(40)
root.right.left = BinaryTree(36)
root.right.left.left = BinaryTree(50)
root.right.left.right = BinaryTree(13)

print('nBynary Tree:n')
root.create_tree(show_tree=True)
print()
print('==='*15)
print()
# --------->  Creating The Doubly Linked List >
print('Doubly Linked List:n')
dll = create_dll(root)
show_ddl(dll)

Output

Bynary Tree:

10 --> 12 --> 25 --> 30 --> 60 --> 77 --> 15 --> 36 --> 50 --> 13 --> 40 -->
=============================================

Doubly Linked List:

25 --> 12 --> 60 --> 30 --> 77 --> 10 --> 50 --> 36 --> 13 --> 15 --> 40 -->