Problem

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

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Examples

Example 1:

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Note that the left child of all nodes should be NULL.

Solution

Method 1 - Recursive

Preorder traversal makes things slightly easy for us, as root access easier since we start with the root. This is what we have to do:

  • Process the root node first, as it is a preorder traversal. So, no changes required in root node
  • Then we flatten the left subtree. How do we do it?
    • Each time we see left subtree, we try to flatten it by putting it before right child:

  • No change needed on right tree.
  • Repeat the process : If we look at it, when we are the left side of the tree, we need to connect tail (or last node) in the left tree to connect to parent’s right child. So, in gist:
TreeNode temp = root.right;
root.right = leftList.head OR root.left;
leftList.tail = temp;

Code

Java
public void flatten(TreeNode root) {
	dfs(root);
}

// helper function
private TreeNode dfs(TreeNode root) {
	if (root == null) {
		return null;
	}
	TreeNode leftTail = dfs(root.left);
	TreeNode rightTail = dfs(root.right);

	if(leftTail != null) {
		leftTail.right = root.right;
		root.right = root.left; // now root.left can be set to null
		root.left = null;
	}
	return rightTail != null? rightTail: (leftTail!= null? leftTail: root)
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Iterative

Here are the steps we follow:

  1. Initialize curr to the root
  2. Iterate through the tree - Continue the loop until all nodes have been processed, i.e. curr is null.
    1. Process the left subtree - If the current node has a left child, we need to flatten the left subtree and reconnect links.
    2. Find the rightmost node of the left subtree, which is leftTail
    3. Now, reassign pointers
      • Connect the rightmost node of the left subtree (leftTail) to the right child of curr (leftTail.right = curr.right).
      • Move the left subtree to the right of curr (curr.right = curr.left).
      • Set the left child of curr to null as required (curr.left = null).

Code

Java
public void flatten(TreeNode root) {
	TreeNode curr = root;
	while (curr != null) {
		if (curr.left != null) {
			var leftTail = root.left;

			while (leftTail.right != null)
				leftTail = leftTail.right;

			leftTail.right = curr.right;
			curr.right = curr.left;
			curr.left = null;
		}
		curr = curr.right;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)