Leetcode.com | 536 Construct binary tree from string | C# solution

Here is my discuss post. 

C# | Recursive function | It is challenging

Sept. 18, 2023

Intuition

It takes time for me to warm up recursive function. I learn how to write a working recursive function to parse the string into a binary tree.

Approach

The following are highlights of successful recursive solution:

1. Tried to solve it by myself first 20 minutes;
2. Studied Leetcode premimum solution called Editorial provided by Leetcode;
3. Studied recursive solution;
4. Wrote a C# solution as well; Spend time to debug
5. Cases in recursive function: left child, right child, and close ')'

Complexity

• Time complexity:

O(N), N is the length of string

• Space complexity:

Code

/**
 * 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 {
    /// <summary>
        /// 536 Construct binary tree from string 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public TreeNode Str2tree(string s)
        {
            return str2treeInternal(s, 0).Item1; 
        }

        /// <summary>
        /// Parse an integer starting from given position - index 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        private Tuple<int, int> getNumber(String s, int index)
        {
            var isNegative = false;

            // A negative number
            if (s[index] == '-')
            {
                isNegative = true;
                index++;
            }

            int number = 0;
            // Use Char.IsDigit to save time
            while (index < s.Length && Char.IsDigit(s[index]))
            {
                number = number * 10 + (s[index] - '0');
                index++;
            }

            return new Tuple<int, int>(isNegative ? -number : number, index);
        }

        /// <summary>
        /// Work on recursive function - basics of recursive function design 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        private Tuple<TreeNode, int> str2treeInternal(string s, int index)
        {
            if (index == s.Length)
            {
                return new Tuple<TreeNode, int>(null, index);
            }

            // Start of the tree will always contain a number representing
            // the root of the tree. So we calculate that first.
            var tuple = getNumber(s, index);

            int value = tuple.Item1;
            index = tuple.Item2;

            var node = new TreeNode(value);                      

            // Next, if there is any data left, we check for the first subtree
            // which according to the problem statement will always be the left child.
            if (index < s.Length && s[index] == '(')
            {
                var data = this.str2treeInternal(s, index + 1);

                node.left = data.Item1;
                index = data.Item2;
            }

            // Indicates a right child
            if (node.left != null && index < s.Length && s[index] == '(')
            {
                var data = this.str2treeInternal(s, index + 1);

                node.right = data.Item1;
                index = data.Item2;
            }

            // 
            return new Tuple<TreeNode, int>(node, index < s.Length && s[index] == ')' ? index + 1 : index);
        }
}