Flatten a Tree Into a Right-Skewed List

medium tree dfs

Problem

Reshape a binary tree in place so that every node's left child is null and the right child points to the next node in the preorder traversal of the original tree.

Walk the tree in reverse-preorder: right, then left, then node. Maintain a single prev pointer; at each node set node.right = prev; node.left = null and update prev = node.

Inputlevel-order: [1, 2, 5, 3, 4, _, 6]

Output1 → 2 → 3 → 4 → 5 → 6

level-order ('_' for null)

def flatten(root):
    prev = [None]
    def visit(node):
        if node is None: return
        visit(node.right)
        visit(node.left)
        node.right = prev[0]
        node.left = None
        prev[0] = node
    visit(root)

function flatten(root) {
  let prev = null;
  function visit(node) {
    if (!node) return;
    visit(node.right);
    visit(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  }
  visit(root);
}

class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

TreeNode* prev_ = nullptr;
void flatten(TreeNode* root) {
    if (!root) return;
    flatten(root->right);
    flatten(root->left);
    root->right = prev_;
    root->left = nullptr;
    prev_ = root;
}

Time: O(n) Space: O(h) recursion depth