Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list":

Another threading problem

Similar to the "Recover Binary Search Tree" problem, we use a threading approach to save on space. When you find a node with a left child, you find that left child's furthest right child and point it to the original node's right child, then switch the original node's left child to be its right child.

I presented this in my data structures and algorithms club and had a lot of fun drawing the pointers out for what this would look like. If you get lost reading this solution, I recommend doing that too!

The hard part

This was the first Go solution for the Tentacles project. Go provided a more significant challenge than adding Python due to its strict typing. For the Binary Tree in particular, you need two different types: a "BinaryTreeRoot" and a "BinaryTree". I took the time to refactor a lot of the tentacles package to get this going, as it had reached the critical state of hard-coding a lot of things. If I have to add another language soon, I think it will go much easier.

Solution

func flatten(root *BinaryTree) *BinaryTree {
	for cur := root; cur != nil; cur = cur.Right {
		if cur.Left != nil {
			thread(cur)
		}
	}
	return root
}

func thread(node *BinaryTree) {
	cur := node.Left
	for cur.Right != nil {
		cur = cur.Right
	}
	cur.Right = node.Right
	node.Right = node.Left
	node.Left = nil
}

Big O Analysis

Time Complexity: O(n)

Explanation: We will have to process each node once.