Flatten Binary Tree explanation

Question

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

Answer 1

When you assign leftmostofright = node, then when the the node does not have a right child, you would create a cycle when this assignment gets executed:

node.right = leftmostofright

That is obviously not what you want to happen. When the node has no right child, you don't want to give it a right child. In that case only None is the correct value for node.right.

Some other remarks:

• There is no need to treat a leaf node any different from other nodes. So you can just omit the if node.left is None and node.right is None: block.

• When a node has no left child, you don't really need to assign to node.left. Same for when there is no right child.

• You can do without leftmostofright and rightmostofleft, by assigning those references directly to node.left and node.right respectively.

And so your helper code could be reduced to just this:

def helper(node):
    leftmost = node
    rightmost = node
    if node and node.left:
        leftmost, node.left = helper(node.left)
        node.left.right = node
    if node and node.right:
        node.right, rightmost = helper(node.right)
        node.right.left = node
    return leftmost, rightmost