Leetcode: Flatten binary tree to linked list C#

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;

{
[TestClass]
{
[TestMethod]
{
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>();
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
{
}
if (curr.right != null)
{
stack.Push(curr.right);
curr.right = null;
}
if (curr.left != null)
{
stack.Push(curr.left);
curr.left = null;
}
}
}
}
}

• I think the moment you do a new Stack(), you violate the restriction to doing it "in-place". You have to move the nodes around in the same tree, without using a helper Commented May 15, 2019 at 21:58
• @fernando yes I think you are right. I will try another solution. Commented May 15, 2019 at 22:18

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

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

• If I put left before right. The result will be wrong Commented May 15, 2019 at 22:17
• Yes, Right before Left is the right order. As left will be processed before Right Commented May 15, 2019 at 23:04