Leetcode discuss: 1028. Recover a Tree From Preorder Traversal

 Here is the link. 

C# Using stack and also mark visited left node

Sept. 7, 2020
1028. Recover a Tree From Preorder Traversal

Introduction
It is my practice for Microsoft phone screen from Vancouver on Sept. 11, 2020. My plan is to go over all tree algorithms and then learn from those tree algorithms.

Case study
Test case 1: A tree with 1-2--3
The tree starts from root node with value 1, and then it's left child with value 2, and then left child with value 3.

Preorder traversal is to start from root node, and the left child, and then right child.
A tree can be constructed from root node, and then if next node has depth with increment 1, then assume that it is left child. In the same time, push node into stack until a node is no longer the child node in the top of stack.

Test case 2: 1-2--3--4
The challenge part is to set node with value 4 as node with 2's right child, not left child.
The idea is to use marked visited HashSet, and then if the top of stack is not parent node of current visited node, then pop up the node.

Node 1 is pushed into stack, and then node with value 2 is pushed into stack, then node with value 3 is pushed into stack; node with value 4 has depth 2, same as node with 3 on top of stack, so pop up stack. In other words, node 3 is popped out, the top of stack is node with value 2, hashSet contains node with value 2, so node with value 2 already has left child, so node with value 4 is right child instead.

The bug I came cross in my first writing is to fall back outside while loop, the current visited node is skipped and then go to next one. I used Microsoft visual studio debugger and then catched the bug. I added nested while loop to continue to check stack if it is not empty.

Hard level algorithm
It is hard level algorithm. But I do think that it is easy to figure out since I worked on medium level algorithm related to preorder traversal. The algorithm is to construct binary tree using preorder and postorder traversal.

I wrote a solution using recursive function, 889. Construct Binary Tree from Preorder and Postorder Traversal is the discussion post.

Time complexity:
O(N) - N is total number of nodes in the tree

space complexity:
average O(logN), height of tree, worst case is O(N)
hashset is also to remove the node once it is visited second time.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode RecoverFromPreorder(string S) {
        // the idea is to push those nodes into stack, and then backtrack based on level comparison
            if (S == null || S.Length == 0)
                return null;

            // parse string 
            // var list = parseNodes(S); // List<int[]> - value, level

            var stack = new Stack<Tuple<TreeNode, int[]>>();

            int index = 0;
            var length = S.Length;

            var rootValue = 0;
            //while(index < length && S[index] >= '0' && S[index] <='9')
            while (index < length && S[index] != '-')
            {
                rootValue = rootValue * 10 + (S[index] - '0');
                index++;
            }

            var rootDepth = 0;
            var root = new TreeNode(rootValue);

            var hashSet = new HashSet<TreeNode>(); // has left child already

            stack.Push(new Tuple<TreeNode, int[]>(root, new int[] { rootValue, rootDepth }));

            // two nodes   - one is left child
            // three nodes - one is left, third one is left's left
            // three nodes - one is left child, one is right child
            while (stack.Count > 0 && index < length)
            {
                var currentDepth = 0;
                while (index < length && S[index] == '-')
                {
                    index++;
                    currentDepth++;
                }

                var currentValue = 0;
                //while(index < length && S[index] >= '0' && S[index] <='9')
                while (index < length && S[index] != '-')
                {
                    currentValue = currentValue * 10 + (S[index] - '0');
                    index++;
                }

                while (stack.Count > 0)
                {
                    var peek = stack.Peek();
                    var peekNode = peek.Item1;
                    var peekDepth = peek.Item2[1];
                    var isChild = currentDepth > peekDepth;

                    // push the current node to the stack
                    if (isChild)
                    {
                        var node = new TreeNode(currentValue);
                        if (!hashSet.Contains(peekNode))
                        {
                            peekNode.left = node; // go to left node as first choice
                            hashSet.Add(peekNode);
                        }
                        else
                        {
                            peekNode.right = node;

                            // to save space - it is also ok to remove node from hashSet
                            hashSet.Remove(peekNode);
                        }

                        stack.Push(new Tuple<TreeNode, int[]>(node, new int[] { currentValue, currentDepth }));
                        break;
                    }
                    else
                    {
                        // or node in the top of stack is a leaf node, pop up, 
                        // push current node into the stack
                        stack.Pop();
                    }
                }
            }

            return root;
    }
}