Leetcode: Flatten binary tree to linked list C#

Question

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 && root.right == null))
            {
                return;
            }
            Stack<TreeNode> stack = new Stack<TreeNode>();
            var head = root;
            stack.Push(root);
            while (stack.Count > 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;
                }
            }
        }
    }
}

Answer 1

The first condition is a bit conservative:

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

Just if (root == null) would be enough, the rest of the implementation naturally handles the cases of root.left == null && 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

Answer 2

Your solution use a single loop to iterate through all elements so the complexity is O(N), where N is the number of elements.

The performance can be improved a little by removing the first if statement and inserting left before right in the stack