<jupyter_start><jupyter_text>Flatten Binary Tree[link](https://www.algoexpert.io/questions/Flatten%20Binary%20Tree)<jupyter_code># This is the class of the input root. Do not edit it.
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def flattenBinaryTree(root):
    # Write your code here.
    pass<jupyter_output><empty_output><jupyter_text>My Solution<jupyter_code># This is the class of the input root. Do not edit it.
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def flattenBinaryTree(root):
    # Write your code here.
    # O(n) time | O(n) space
    arrayOfNodes = []
    flattenHelper(root, arrayOfNodes)
    for i in range(len(arrayOfNodes) - 1):
        arrayOfNodes[i].right = arrayOfNodes[i + 1]
        arrayOfNodes[i + 1].left = arrayOfNodes[i]
    return arrayOfNodes[0]
    
    
def flattenHelper(node, array):
    if node is not None:
        flattenHelper(node.left, array)
        array.append(node)
        flattenHelper(node.right, array)
# This is the class of the input root. Do not edit it.
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# O(n) time | O(d) space
def flattenBinaryTree(root):
    # Write your code here.
    leftMost, _ = getLeftRightMost(root)
    return leftMost

def getLeftRightMost(node):
    if node.left is None:
        leftMost = node
    else:
        leftMostOfLeftSubtree, rightMostOfLeftSubtree = getLeftRightMost(node.left)
        connectNodes(rightMostOfLeftSubtree, node)
        leftMost = leftMostOfLeftSubtree
        
    if node.right is None:
        rightMost = node
    else:
        leftMostOfRightSubtree, rightMostOfRightSubtree = getLeftRightMost(node.right)
        connectNodes(node, leftMostOfRightSubtree)
        rightMost = rightMostOfRightSubtree
    
    return leftMost, rightMost

def connectNodes(leftNode, rightNode):
    leftNode.right = rightNode
    rightNode.left = leftNode<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code>class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# O(n) time, O(n) space - where n is the number of nodes in the Binary Tree
def flattenBinaryTree(root):
    inOrderNodes = getNodesInOrder(root, [])
    for i in range(0, len(inOrderNodes) - 1):
        leftNode = inOrderNodes[i]
        rightNode = inOrderNodes[i + 1]
        leftNode.right = rightNode
        rightNode.left = leftNode
    return inOrderNodes[0]

def getNodesInOrder(tree, array):
    if tree is not None:
        getNodesInOrder(tree.left, array)
        array.append(tree)
        getNodesInOrder(tree.right, array)
    return array
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# O(n) time, O(d) space - where n is the number of nodes in the Binary Tree 
# and d is the depth (height) of the Binary Tree
def flattenBinaryTree(root):
    leftMost, _ = flattenTree(root)
	return leftMost

def flattenTree(node):
	if node.left is None:
		leftMost = node
	else:
		leftSubtreeLeftMost, leftSubtreeRightMost = flattenTree(node.left)
		connectNodes(leftSubtreeRightMost, node)
		leftMost = leftSubtreeLeftMost
		
	if node.right is None:
		rightMost = node
	else:
		rightSubtreeLeftMost, rightSubtreeRightMost = flattenTree(node.right)
		connectNodes(node, rightSubtreeLeftMost)
		rightMost = rightSubtreeRightMost
		
	return [leftMost, rightMost]

def connectNodes(left, right):
	left.right = right
	right.left = left<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08910123966942149, 'fraction_numerical': 0.0030991735537190084, 'mean_word_length': 3.2420591456736036, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '383208', 'license': 'MIT', 'n_tokens_mistral': 1265, 'n_tokens_neox': 1232, 'n_words': 327, 'path': 'algoExpert/flatten_binary_tree/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '3872'}