Leetcode discuss: 106. Construct Binary Tree from Inorder and Postorder Traversal

July 11, 2022

Here is the link. 

106. Construct Binary Tree from Inorder and Postorder Traversal
     Assuming that duplicate value is not existing.

July 20, 2020
Introduction
Tree algorithm is always my favorite. I learn so many things in terms of C# programming from 2016 to 202. I like to write a solution first, and then review my old submission code written in Sept. 2016. Welcome comments for my C# code. I strive to make improvements and be a quick learner.

Case study | Propose a solution
Given a simple tree, root node with value 1, left child with value 2, right child with value 3.
Inorder traversal is to visit left child, root and right child, the output is [2, 1, 3]; whereas postorder traversal is to visit root node, left child and then right child, the output is [1, 2, 3].

Since last element in postorder traversal result is root node, then it is a good idea to search inorder traversal result and find root node, so that we know that the left subtree inorder subarray and right subtree subarray.

The root node is solved, and left subtree and right subtree is same subproblem which can be solved using recursive function.

One more tip
In order to find unique value in inorder traversal result, it takes O(1) time to lookup. The idea is to preprocess the inorder traversal result and build a hashmap, so given a value, the position of value in inorder traversal will be retrieved in O(1) time.

Solution 1: Written on July 6, 2022
I like to share my practice on July 6, 2022 first.

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

namespace _106_inorder_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 inorder = new int[] {9,3,15,20,7};
            var postorder = new int[] { 9, 15, 7, 20, 3 };
            var root = BuildTree(inorder, postorder);
            Debug.Assert(root.val == 3 && root.left.val == 9 && root.right.val == 20 
                && root.right.left.val == 15 && root.right.right.val == 7);
        }

        static Dictionary<int, int> inorderMap = new Dictionary<int, int>();

        /// <summary>
        /// Given constraints:
        /// 1. Inorder and postorder consist of unique values.
        /// 2. Each value of postorder also appears in inorder.
        /// 3. inorder is guaranteed to be the inorder traversal of the tree.
        /// 4. postorder is guaranteed to be the postorder traversal of the tree.
        /// </summary>
        /// <param name="inorder"></param>
        /// <param name="postorder"></param>
        /// <returns></returns>
        public static TreeNode BuildTree(int[] inorder, int[] postorder)
        {
            var postOrderLength = postorder.Length;
            if (postOrderLength == 0)
            {
                return null;
            }

            inorderMap.Clear();

            // Constraints 1: Inorder and postorder consist of unique values.
            var inorderLength = inorder.Length;     
            for (int i = 0; i < inorderLength; i++)
            {
                inorderMap[inorder[i]] = i;
            }

            return build(inorder, 0, inorderLength - 1,
                postorder, 0, postOrderLength - 1);
        }

        /// <summary>
        /// build a binary tree using inorder and postorder traversal
        /// Find root node, and then root node's left child and right child 
        /// using recursive function
        /// </summary>
        /// <param name="inorder"></param>
        /// <param name="first1"></param>
        /// <param name="last1"></param>
        /// <param name="postorder"></param>
        /// <param name="first2"></param>
        /// <param name="last2"></param>
        /// <returns></returns>
        private static TreeNode build(int[] inorder, int first1, int last1,
            int[] postorder, int first2, int last2)
        {
            // base case
            if (first1 > last1 || first2 > last2)
            {
                return null;
            }

            // root node - last value in post order traversal 
            var root = new TreeNode(postorder[last2]);

            var value = postorder[last2];              
            var rootIndex = (int)inorderMap[value];            

            // count - the size of left subtree, how many nodes 
            int leftSubTreeCount = rootIndex - first1;                 

            // left subtree - find inorder and postorder range accordingly
            int start1 = first1;
            int end1 = rootIndex - 1;

            int start2 = first2;
            int end2 = first2 + leftSubTreeCount - 1;

            root.left = build(inorder, start1, end1, postorder, start2, end2);

			// right subtree - find inorder and postorder range accordingly
            start1 = rootIndex + 1;
            end1 = last1;
            start2 = first2 + leftSubTreeCount;
            end2 = last2 - 1;

            root.right = build(inorder, start1, end1, postorder, start2, end2);

            return root;
        }
    }
}

Solution 2: written in Sept. 2016 | My code review | Things to work on
I like to review my own code written in Sept. 2016. I found so many issues in the code. I like to document my practice and encourage myself to work hard, and continuously make improvements.

If you read here, then you may choose to skip the following C# code review.

Code Review

1. Introduce strong data type data structure!
2. Instead of using C# HashTable, using Dictionary<int, int>; Compile time data type checking is better than runnng time data type checking.
3. It is better to write a discuss post and track progress.
4. Avoid array copy, use index positions of array
5. Use meaningful variable names, do not using abbreviations. Please use good and meaningful variable names. Read The ART of Readable Code book.

The following C# code passes online judge.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    Hashtable htable = new Hashtable();
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        int p_l = postorder.Length; 
            if(p_l == 0 ) {
                return null;
            }

            int i_l = inorder.Length;     // key value is unique, otherwise rewrite the value.  key: node value,k value: index 
            for(int i = 0; i < i_l; i++) {
                htable[inorder[i]] = i;
            }

            return build(inorder, 0, i_l - 1,
                postorder, 0,  p_l- 1);
        }
        
        public  TreeNode build(int[] inorder, int s0, int e0,
            int[] postorder, int s1, int e1) {
            if(s0 > e0 || s1 > e1) {
                return null;
            }

            TreeNode root = new TreeNode(postorder[e1]);

            int v = postorder[e1];              // v - root value 
            int p = (int)htable[v];             // p - root position in inorder traversal array 

            int count = p - s0;                 // count - the size of left subtree, how many nodes 

            int start1 = s0;                
            int end1   = p - 1;         
            int start2 = s1;                
            int end2   = s1 + count - 1;    

            root.left = build(inorder, start1, end1, postorder, start2, end2);

            start1 = p + 1;               
            end1   = e0;
            start2 = s1 + count;
            end2   = e1 - 1; 

            root.right = build(inorder, p + 1, e0, postorder, s1 + count, e1 - 1);

            return root;
        }
}