Construct Binary Tree from String

medium tree string stack recursion

Problem

A binary tree is encoded as a string: integer + zero/one/two '(child)' groups. Build the tree.

Inputs = "4(2(3)(1))(6(5))"

Outputtree with root 4, left 2(3,1), right 6(5,_)

Cursor-based recursion; balance parens to slice each child substring.

encoded string

def str2tree(s):
    if not s: return None
    i = 0; n = len(s)
    def parse(i):
        j = i
        if s[j] == "-": j += 1
        while j < n and s[j].isdigit(): j += 1
        node = { "val": int(s[i:j]), "left": None, "right": None }
        if j < n and s[j] == "(":
            node["left"], j = parse_paren(j)
        if j < n and s[j] == "(":
            node["right"], j = parse_paren(j)
        return node, j
    def parse_paren(j):
        assert s[j] == "("; j += 1
        child, j = parse(j)
        assert s[j] == ")"; return child, j + 1
    return parse(0)[0]

function str2tree(s) {
  if (!s) return null;
  let i = 0;
  function parse() {
    let j = i;
    if (s[j] === "-") j++;
    while (j < s.length && s[j] >= "0" && s[j] <= "9") j++;
    const node = { val: Number(s.slice(i, j)), left: null, right: null };
    i = j;
    if (s[i] === "(") { i++; node.left = parse(); i++; }
    if (s[i] === "(") { i++; node.right = parse(); i++; }
    return node;
  }
  return parse();
}

class Solution {
    int i = 0;
    public TreeNode str2tree(String s) {
        if (s.isEmpty()) return null;
        return parse(s);
    }
    TreeNode parse(String s) {
        int j = i;
        if (s.charAt(j) == '-') j++;
        while (j < s.length() && Character.isDigit(s.charAt(j))) j++;
        TreeNode node = new TreeNode(Integer.parseInt(s.substring(i, j)));
        i = j;
        if (i < s.length() && s.charAt(i) == '(') { i++; node.left = parse(s); i++; }
        if (i < s.length() && s.charAt(i) == '(') { i++; node.right = parse(s); i++; }
        return node;
    }
}

int idx = 0;
TreeNode* parse(string& s) {
    int j = idx;
    if (s[j] == '-') j++;
    while (j < (int)s.size() && isdigit(s[j])) j++;
    TreeNode* node = new TreeNode(stoi(s.substr(idx, j - idx)));
    idx = j;
    if (idx < (int)s.size() && s[idx] == '(') { idx++; node->left = parse(s); idx++; }
    if (idx < (int)s.size() && s[idx] == '(') { idx++; node->right = parse(s); idx++; }
    return node;
}
TreeNode* str2tree(string s) { idx = 0; return s.empty() ? nullptr : parse(s); }

Explanation

The tree is written as text like 4(2(3)(1))(6(5)): a number, then up to two parenthesised groups for its left and right children. We rebuild it with a recursive parser that walks the string left to right using a shared cursor i.

Each call to parse first reads a full integer (handling a leading - and then the digits) and makes a node from it. The cursor stops on whatever character comes after the number.

If that character is (, the next group is the left child, so we step past the (, recurse to build the child, then step past the matching ). If another ( follows, the same thing happens for the right child. Missing groups simply stay null.

Example: 4(2(3)(1))(6(5)). Read 4, then its first group builds left child 2, whose own two groups give children 3 and 1. Back at 4, the second group builds right child 6, which has a single left child 5.

Because the cursor only ever moves forward and each character is read once, the parse runs in linear time and naturally mirrors the nesting of the parentheses.

Time: O(n) Space: O(h)