Here is my (non-trivial, old-fashioned) solution. Obviously, from the first sight, I can use DFS to traverse the tree. I like to do DFS recursively. I do use a stack to keep track of the val in nodes, but I could have used a queue instead. When making the flatten tree, I again use a recursive approach.
## push the node vals in a stack, with right-most in the bottom, post-order traversal fashion def pushNodesInStack(root, stack): if (root == None): return stack if not root.right == None: stack = pushNodesInStack(root.right, stack) if not root.left == None: stack = pushNodesInStack(root.left, stack) stack.append(root.val) return stack ## recursively set the right val all the way up to root def setRight(root, stack): if len(stack) == 0: return None root.left = None root.val = stack.pop() root.right = setRight(TreeNode(0), stack) return root class Solution(object): def flatten(self, root): stack =  pushNodesInStack(root, stack) root = setRight(root, stack)