2
\$\begingroup\$

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;
                }
            }
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – fernando.reyes May 15 at 21:58
  • \$\begingroup\$ @fernando yes I think you are right. I will try another solution. \$\endgroup\$ – Gilad May 15 at 22:18
3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ If I put left before right. The result will be wrong \$\endgroup\$ – Gilad May 15 at 22:17
  • \$\begingroup\$ Yes, Right before Left is the right order. As left will be processed before Right \$\endgroup\$ – Serge Obally May 15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.