I am trying to solve a problem about flattening Binary tree into a linked list type structure. I will write the problem description here as well
Write a function that takes in a Binary Tree, flattens it, and returns its leftmost node. A flattened Binary Tree is a structure that's nearly identical to a Doubly Linked List (except that nodes have left and right pointers instead of prev and next pointers), where nodes follow the original tree's left-to-right order. Note that if the input Binary Tree happens to be a valid Binary Search Tree, the nodes in the flattened tree will be sorted. The flattening should be done in place, meaning that the original data structure should be mutated. Each BinaryTree node has an integer value, a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null.
My code:
class BinaryTree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def flattenBinaryTree(root):
a, b = helper(root)
return a
pass
def helper(node):
if node is None:
return None, None
if node.left is None and node.right is None:
return node, node
print(node.value)
leftmostofleft = node
rightmostofright = node
leftmostofright = None
rightmostofleft = None
if node.left:
leftmostofleft, rightmostofleft = helper(node.left)
if node.right:
leftmostofright, rightmostofright = helper(node.right)
node.right = leftmostofright
if leftmostofright:
leftmostofright.left = node
node.left = rightmostofleft
if rightmostofleft:
rightmostofleft.right = node
return leftmostofleft, rightmostofright
My issue
The code that i put here works. but my issue what i don't understand is in these lines.
leftmostofleft = node
rightmostofright = node
leftmostofright = None
rightmostofleft = None
These are default values in case node does not have a left or does not have a right. so, i figured if node doesn't have a left child or subtree at all, the leftmostofleft would be node same with the right. but what i dont understand is why the leftmostofright and rightmostofleft has to be None. shouldn't they be node too? since the leftmost of right values of subtree is value of node too? In short if i change the above block of code to this
leftmostofleft = node
rightmostofright = node
leftmostofright = node
rightmostofleft = node
it doesn't work. I do think it will create duplicates maybe if i did that, but I would like an explanation if possible?
Testing code
import program
import unittest
class TestProgram(unittest.TestCase):
def test_case_1(self):
root = BinaryTree(1).insert([2, 3, 4, 5, 6])
root.left.right.left = BinaryTree(7)
root.left.right.right = BinaryTree(8)
leftMostNode = program.flattenBinaryTree(root)
leftToRightToLeft = leftMostNode.leftToRightToLeft()
expected = [4, 2, 7, 5, 8, 1, 6, 3, 3, 6, 1, 8, 5, 7, 2, 4]
self.assertEqual(leftToRightToLeft, expected)
class BinaryTree(program.BinaryTree):
def insert(self, values, i=0):
if i >= len(values):
return
queue = [self]
while len(queue) > 0:
current = queue.pop(0)
if current.left is None:
current.left = BinaryTree(values[i])
break
queue.append(current.left)
if current.right is None:
current.right = BinaryTree(values[i])
break
queue.append(current.right)
self.insert(values, i + 1)
return self
def leftToRightToLeft(self):
nodes = []
current = self
while current.right is not None:
nodes.append(current.value)
current = current.right
nodes.append(current.value)
while current is not None:
nodes.append(current.value)
current = current.left
return nodes