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?
Advertisement
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:
- Go down to the most left Node which becomes the HEAD.
- 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
- Caluclate the current node, its previous and the Right node from the Previoys.
- 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 -->