Construct Binary tree from string

XXX. Construct Binary Tree from String

Binary Tree

Recursion

Parsing

Problem Statement:

Given a string representing a binary tree in the format root(left_subtree)(right_subtree), construct the binary tree. Parentheses are used to denote subtrees, and all integer values in the input are valid.

For example: "4(2(3)(1))(6(5))" represents the following tree:

                4
               / \
              2   6
             / \  /
            3   1 5
        

Algorithm:

1. Parse the input string to extract the root node value. The root value is located at the start of the string until the first parenthesis.
2. Recursively parse the left and right subtrees:
   • For the left subtree, locate the substring within the first set of parentheses.
   • For the right subtree, locate the substring within the second set of parentheses.
3. Construct the tree by creating a TreeNode for the root and attaching the left and right child nodes returned by the recursive calls.
4. Return the constructed tree.

Complexity:

Time Complexity: O(n), where n is the length of the string. Each character is processed once.
Space Complexity: O(h), where h is the height of the tree (due to recursion stack).

Java Implementation:

public TreeNode str2tree(String s) {
    // Base case: If the string is empty, return null
    if (s.length() == 0) return null;

    // Parse the root value
    int i = 0, j = 0;
    while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) 
        j++;

    // Create the root node with the parsed value
    TreeNode root = new TreeNode(Integer.parseInt(s.substring(i, j)));

    // Parse the left child (if present)
    if (j < s.length()) {
        i = j; // Update starting index for the left child
        int count = 1; // Use a counter to match parentheses
        while (j + 1 < s.length() && count != 0) {
            j++;
            if (s.charAt(j) == ')') count--;
            if (s.charAt(j) == '(') count++;
        }
        // Recursive call for the left subtree
        root.left = str2tree(s.substring(i + 1, j));
    }

    j++; // Move to the start of the right child (if present)

    // Parse the right child (if present)
    if (j < s.length()) 
        root.right = str2tree(s.substring(j + 1, s.length() - 1));

    // Return the constructed tree
    return root;
}