Leetcode: Flatten binary tree to linked list C# https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Please comment on performance


  Given a binary tree, flatten it to a linked list in-place.
  
  For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

  
  The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6



using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LinkedListQuestions
{
    [TestClass]
    public class FlattenBinaryTree2LinkedList
    {
        [TestMethod]
        public void FlattenBinaryTree2LinkedListTest()
        {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(5);
            root.left.left = new TreeNode(3);
            root.left.right = new TreeNode(4);
            root.right.right = new TreeNode(6);
            Flatten(root);
            Assert.AreEqual(1, root.data);
            Assert.AreEqual(2, root.right.data);
            Assert.AreEqual(3, root.right.right.data);
            Assert.AreEqual(4, root.right.right.right.data);
            Assert.AreEqual(5, root.right.right.right.right.data);
            Assert.AreEqual(6, root.right.right.right.right.right.data);

        }
        public void Flatten(TreeNode root)
        {
            if (root == null || (root.left == null &amp;&amp; root.right == null))
            {
                return;
            }
            Stack&lt;TreeNode&gt; stack = new Stack&lt;TreeNode&gt;();
            var head = root;
            stack.Push(root);
            while (stack.Count &gt; 0)
            {
                var curr = stack.Pop();
                if (curr != root) // in the first iteration, we don't want to move the head to the next item
                {
                    head.right = curr;
                    head = curr;
                }
                if (curr.right != null)
                {
                    stack.Push(curr.right);
                    curr.right = null;
                }
                if (curr.left != null)
                {
                    stack.Push(curr.left);
                    curr.left = null;
                }
            }
        }
    }
}
The first condition is a bit conservative:


if (root == null || (root.left == null &amp;&amp; root.right == null))



Just if (root == null) would be enough, the rest of the implementation naturally handles the cases of root.left == null &amp;&amp; root.right == null.



Evaluating curr != root for every node, when it's only useful for the first node is a bit ugly.
You could get rid of that by not adding root itself on the stack, but its children. (In the right order, and when not null.)



head is a misleading name for a variable that traverses all the nodes,
especially since the end result is effectively a linked list,
where "head" usually means the first element.
I'd rename this to node.



All the curr.right = null; can be safely dropped,
because curr.right will either get overwritten with the intended value,
or it's null to begin with (in the very last node).



An \$O(n)\$ solution exists without using a stack:


When left is null and right is not, advance over right
When right is null and left is not, move left to right and advance over right
When both not null of node, then:


traverse through all the right descendants of node.left, and append at the end node.right
move node.left to node.right and advance over it