Leetcode discuss: 889. Construct Binary Tree from Preorder and Postorder Traversal

 Here is the link. 

C# Find right subtree root node in postorder traversal list

Sept. 10, 2020
889. Construct Binary Tree from Preorder and Postorder Traversal

Introduction

The idea to solve the problem is simple and easy to figure out. I will go over a simple example to explain it first, but the coding is hard and I needed to use Microsoft Visual studio debugger and then figure out how to set condition if statement to terminate subtree. My bug is to put all nodes in right subtree, and never set left subtree for some reason.

Case study
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
The root node is the first one in preorder, and also last one in post order. The idea is to work on next one, post order traveral list next to last is 3, which is right subtree root node.

By looking up inorder traversal list, the index position of 3 is 4, so preorder list is divided into left subtree [2, 4, 5], right subtree [3, 6, 7].

The idea is to put postorder traversal list to a stack, and keep working on a number at a time.

What is challenge part of problem solving? I did not know until I found the code does not put left child for any subtree.

Check if next node in post order stack is not in current subtree
It took me over 15 minutes debugging to find out that if condition statement is needed. First, I have to simplify the test case, and make sure that simple test works.
pre = [1, 2, 3]
post = [2, 3, 1]

When I interviewed people using the algorithm recently as a mock interviewer, one chose not to write the code, but he came out the idea to find right subtree's root node; Second one did not add if condition statement to enclose root.right and root.left statement. As an interviewer, I did not write the code first, so I did not know the issue. In other words, I need to point out the design issue, it is important part of recursive thinking challenge most people fail in their first writing.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _889_preorder_and_postorder
{
    class Program
    {
        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;
            }
        }

        static void Main(string[] args)
        {
            //var pre = new int[]{1,2,4,5,3,6,7};
            //var post = new int[]{4,5,2,6,7,3,1};

            var pre  = new int[] { 1, 2, 3 };
            var post = new int[] { 2, 3, 1 };

            var root = ConstructFromPrePost(pre, post);
        }

        /// pre  = [1,2,4,5,3,6,7]
        /// post = [4,5,2,6,7,3,1]
        /// Output: [1,2,3,4,5,6,7]
        /// space complexity: O(N), N is total number of nodes
        /// time complexity: O(N), lookup using hashMap O(1), 
        public static TreeNode ConstructFromPrePost(int[] pre, int[] post) {
            if (pre == null || post == null || pre.Length != post.Length)
            {
                return null;
            }

            var stack = new Stack<int>(post);
            var map = new Dictionary<int, int>();
            for (int i = 0; i < pre.Length; i++)
            {
                map.Add(pre[i], i);
            }

            // construct the tree using postorder, and then find right subtree
            // root node using postorder traversal
            return constructTreeUsingPostOrder(pre, 0, pre.Length - 1, stack, map);
        }

        private static TreeNode constructTreeUsingPostOrder(int[] pre, int preStart, int preEnd, Stack<int> post, Dictionary<int, int> map)
        {
            if (post.Count == 0 || preStart > preEnd)
            {
                return null; 
            }

            var rootVal = post.Pop();
            var root = new TreeNode(rootVal);

            if (post.Count == 0)
            {
                return root; 
            }

            var rightValue = post.Peek();
            var rightIndex = map[rightValue];

            if (rightIndex <= preEnd && rightIndex >= preStart) // added after debugging - if it is in the subtree
            {
                root.right = constructTreeUsingPostOrder(pre, rightIndex, preEnd, post, map);
                root.left  = constructTreeUsingPostOrder(pre, preStart + 1, rightIndex - 1, post, map);
            }            

            return root; 
        }
    }
}