Construct Binary Tree from String with Bracket Representation

The problem, simply

You get a string that describes a binary tree. It starts with a number, the root. After the number there can be up to two bracket pairs. The first pair holds the left child's whole description, and the second pair holds the right child's. Inside each pair the same rule repeats.

Build the tree and give back its root. Numbers can have several digits and can be negative. An empty pair () means "no left child here", so that a right child can follow.

A story to remember it

Picture it

Examples

Way 1: the simple way

For a piece of the string, read the number, then find where its first bracket pair closes by counting brackets. Build the left child from the inside of that pair. Then do the same for the second pair.

1. Read the number at the start of the piece.
2. If an open bracket follows, walk forward counting: ( adds 1, ) takes 1. When the count hits 0, that is the matching close.
3. Build the left child from the inside. If another pair follows, find its close the same way and build the right child.

class Solution {
    public TreeNode treeFromString(String s) {
        if (s == null || s.isEmpty()) return null;
        return build(s, 0, s.length() - 1);
    }

    private TreeNode build(String s, int lo, int hi) {
        if (lo > hi) return null;                       // an empty pair
        int i = lo, sign = 1, num = 0;
        if (s.charAt(i) == '-') { sign = -1; i++; }
        while (i <= hi && Character.isDigit(s.charAt(i))) num = num * 10 + (s.charAt(i++) - '0');
        TreeNode node = new TreeNode(sign * num);
        if (i > hi) return node;                        // no brackets
        int close = match(s, i);
        node.left = build(s, i + 1, close - 1);
        if (close + 1 <= hi) {
            int close2 = match(s, close + 1);
            node.right = build(s, close + 2, close2 - 1);
        }
        return node;
    }

    // index of the bracket that closes the one at 'open'
    private int match(String s, int open) {
        int depth = 0;
        for (int j = open; ; j++) {
            if (s.charAt(j) == '(') depth++;
            else if (s.charAt(j) == ')' && --depth == 0) return j;
        }
    }
}

How long it takes: each node scans its whole bracket pair to find the close. A deep chain like 1(2(3(4(5)))) scans the inner part again and again, O(n^2). Extra room: the waiting helpers, up to O(n) deep.

Way 2: the clever way

Never scan ahead. Keep one finger i on the string that only moves forward. A helper reads its number, and if it sees (, it steps over it and asks a new helper to build the left child. That helper stops exactly at the matching ), so the finger is already in the right place. Step over the ) and do the same for a right child.

1. If the finger is on ) or past the end, there is no node here (an empty pair).
2. Read the sign and the digits, and make a node.
3. If the finger is on (: step over it, build the left child, step over the ).
4. If the finger is on ( again: step over it, build the right child, step over the ).

class Solution {
    private int i;   // the finger, shared by every helper

    public TreeNode treeFromString(String s) {
        i = 0;
        if (s == null || s.isEmpty()) return null;
        return build(s);
    }

    private TreeNode build(String s) {
        if (i >= s.length() || s.charAt(i) == ')') return null;   // empty pair like ()
        int sign = 1, num = 0;
        if (s.charAt(i) == '-') { sign = -1; i++; }
        while (i < s.length() && Character.isDigit(s.charAt(i))) num = num * 10 + (s.charAt(i++) - '0');
        TreeNode node = new TreeNode(sign * num);
        if (i < s.length() && s.charAt(i) == '(') {
            i++;                        // step over (
            node.left = build(s);
            i++;                        // step over )
        }
        if (i < s.length() && s.charAt(i) == '(') {
            i++;
            node.right = build(s);
            i++;
        }
        return node;
    }
}

How long it takes: the finger visits each character once, O(n). Extra room: the waiting helpers, as many as the tree is tall, O(h).

Watch out for

• An empty pair (). Without the ) check at the start, the helper makes a node with value 0 out of nothing.
• Moving the finger past a ) that belongs to the parent. Each helper steps over only the brackets it opened.
• Using a local copy of the finger. Every helper must move the same shared finger, so keep it in a field (or pass an int[]).

What interviewers ask next

• The other direction, tree to string? Write the value, then (left) if there is a left child, then (right) if there is a right child. Write () for a missing left child only when a right child follows. That is LeetCode 606.
• Without recursion? Use a stack of nodes. A number makes a node that you attach to the top of the stack (left if empty, else right) and push. A ) pops. This handles the same input in O(n).
• Can it fail? With bad input, like an unclosed bracket. Ask if you should check for that.
• Serialize and deserialize any tree? Same idea with a marker for empty children, for example 1,2,#,#,3,#,# in preorder (LeetCode 297).

Remember this

Grown-up words: the boxes inside boxes are nested parentheses, reading them with helpers is recursive descent parsing, the finger is a shared index, and the helpers waiting are the call stack.