Flatten Binary Tree to Linked List

Given a binary tree, return a flattened tree

Note: do it in-place, i.e. update the original tree rather than creating a new one

// Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}

 

Example

Input:     1   
          / \  
         2   3 

Output:    1
          / \
       null  2
            / \
         null  3

As usual, we are starting by understanding the problem. Let's see a more complex example.

After flattening the tree, we should get this

To flatten the tree, we should visit a right node after a left one. To simulate this traverse, we will use stack.

• push the root node into the stack
• until the stack is not empty
  • pop the top node
  • push its right node into the stack. We push the right node first because the stack is a LIFO data structure
  • push its left node into the stack
  • if the stack is not empty
    • set right node equals to top of the stack. We do it thru the Peak operation. Peak returns a reference to the top item (i.e. item still in the stack)
  • set the left node to null

Code

    public TreeNode Flatten(TreeNode root)
    {
        if (root == null)
        {
            return null;
        }

        var stack = new Stack<TreeNode>();
        stack.Push(root);

        while (stack.Count != 0)
        {
            TreeNode current = stack.Pop();
            if (current.Right != null)
            {
                stack.Push(current.Right);
            }

            if (current.Left != null)
            {
                stack.Push(current.Left);
            }

            if (stack.Count != 0)
            {
                current.Right = stack.Peek();
            }

            current.Left = null;
        }

        return root;
    }

Time Complexity: O(n), space complexity: O(n)