Construct Binary Tree from String

Medium

Construct Binary Tree from String

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input string? Can you provide a few more examples to illustrate the string structure representing the tree?
What should I return if the input string is empty or invalid (e.g., malformed string that doesn't represent a valid binary tree)?
Are the node values in the string guaranteed to be integers, or could they be other data types (e.g., strings)?
Are there any constraints on the range of integer values for the nodes in the tree?
Is the input string guaranteed to represent a complete or full binary tree, or can it be any arbitrary binary tree?

Brute Force Solution

Approach

The goal is to build a tree from a string that represents the tree's structure. The brute force method explores every possible tree arrangement, even if it's inefficient. It's like trying every single arrangement of branches and nodes until you find one that matches the string's description.

Here's how the algorithm would work step-by-step:

Start by considering the very first character or number in the string as the root of the tree.
Then, try to figure out if this root has any children by looking at the characters immediately following it in the string. If there are parentheses, those hint at possible children.
For each potential child, treat the substring representing it as a separate, smaller tree to build, applying this same process again to determine its root and its children.
If the string has multiple possible ways to interpret the child nodes (say, different ways to split up the parts in parentheses), try building the tree each way.
Keep going, recursively building smaller and smaller subtrees, until you've explored all possible ways to interpret the original string as a tree.
Check if the tree that you built matches the structure implied by the whole string. If it does, you've found a valid solution; otherwise, keep trying other possibilities.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def construct_binary_tree_from_string_brute_force(tree_string):

    def parse_tree_string(substring, index):
        if index >= len(substring):
            return None, index

        # Extract node value
        start = index
        while index < len(substring) and substring[index].isdigit():
            index += 1
        
        if start == index:
            return None, index # No node value found
        
        node_value = int(substring[start:index])
        new_node = TreeNode(node_value)

        # Check for left child
        if index < len(substring) and substring[index] == '(': 
            index += 1
            new_node.left, index = parse_tree_string(substring, index)

            # Check if left parsing successful before right
            if new_node.left:
                if index < len(substring) and substring[index] == '(': 
                    index += 1
                    new_node.right, index = parse_tree_string(substring, index)
                    if new_node.right and index < len(substring) and substring[index] == ')':
                        index += 1
                        return new_node, index
                    else:
                        return None, len(substring) # Invalid structure
                elif index < len(substring) and substring[index] == ')':
                    index += 1
                    return new_node, index #Only left child exists
                else:
                    return None, len(substring) #Error when parsing
            else:
                return None, len(substring)

        # If no children and only a number return
        return new_node, index
    
    root, _ = parse_tree_string(tree_string, 0)
    return root

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible binary tree structures that can be formed from the input string of length n. At each step, the algorithm considers different ways to split the string to form left and right subtrees, leading to exponential branching. Specifically, for each node, there can be multiple ways to interpret the substrings as subtrees, leading to overlapping subproblems and recalculations. The number of possible binary trees grows exponentially with the number of nodes, approximating a complexity of O(2^n) in the worst case where every split needs to be explored.

Space Complexity

O(N) – The dominant factor in space complexity arises from the recursive calls to build subtrees. In the worst-case scenario, the string represents a highly unbalanced tree, leading to a maximum recursion depth proportional to the input string length N. Each recursive call creates a new stack frame, storing local variables and the return address. Therefore, the space used by the call stack can grow up to O(N). While other variables might be used, the recursion depth governs the overall auxiliary space.

Optimal Solution

Approach

The best way to build the tree from the string is to process the string piece by piece, using a system to understand the structure. We use something like a temporary holding area to keep track of where we are in the tree-building process as we go.

Here's how the algorithm would work step-by-step:

First, we read the initial number from the string, which becomes the very top node of our tree.
If we see an opening parenthesis '(', that means we're about to build a child of the current node. So, we make the current node our active focus.
Next, we read the number immediately after the parenthesis. This new number becomes the left child of the active node.
After adding the left child, we make the left child the new active node if another '(' follows it.
If instead we see another number after a '(', it will become the right child. If a ')' follows, it just means we've finished adding children to this node, so we go back up to the parent node.
If a closing parenthesis ')' appears, we're done with the current node and need to return to the parent node, effectively going one level up in the tree.
We repeat this process of reading numbers, making them nodes, connecting them as children based on the parentheses, and keeping track of the 'current' node, until we've processed the entire string.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def construct_binary_tree_from_string(tree_string):
    if not tree_string:
        return None

    current_position = 0
    def parse_tree():
        nonlocal current_position

        # Extract number for the current node.
        start = current_position
        while current_position < len(tree_string) and tree_string[current_position].isdigit() or tree_string[current_position] == '-':
            current_position += 1
        
        if start == current_position:
            return None

        node_value = int(tree_string[start:current_position])
        current_node = TreeNode(node_value)

        # Check if left child exists.
        if current_position < len(tree_string) and tree_string[current_position] == '(': 
            current_position += 1
            current_node.left = parse_tree()

            # Parse the rest of the string.
            if current_position < len(tree_string) and tree_string[current_position] == ')':
                current_position += 1

        # Check if right child exists.
        if current_position < len(tree_string) and tree_string[current_position] == '(': 
            current_position += 1
            current_node.right = parse_tree()

            # Parse the rest of the string.
            if current_position < len(tree_string) and tree_string[current_position] == ')':
                current_position += 1

        return current_node
    
    # Initiate tree construction, parsing the whole string.
    root = parse_tree()
    return root

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm processes the input string character by character, where n represents the length of the string. Each character is examined and used to construct a binary tree node or adjust the current node pointer based on parentheses. Since each character is visited a constant number of times, the time complexity is directly proportional to the input string's length. Thus, the algorithm exhibits linear time complexity, O(n).

Space Complexity

O(N) – The provided explanation describes a tree construction process using a stack-like structure (the 'temporary holding area' or 'active focus') to keep track of the current node and its ancestors as we traverse the input string. In the worst-case scenario, where the tree is highly skewed, this stack could grow to a depth proportional to the number of nodes, N, in the tree, where N is also related to the length of the input string. Therefore, the auxiliary space used for tracking the current node and its parents could grow linearly with N. This implies a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return null, indicating an invalid tree cannot be constructed.
String with only parenthesis '()'	Return null as '()' doesn't define a valid node value.
String with a single node value and no children e.g., '4'	Create a single node tree with the value 4 and return it.
String with improperly nested parentheses, e.g., '(4(2)(3)))'	Throw an exception indicating an invalid string format.
String with non-numeric characters within node values, e.g., '(4a(2)(3))'	Throw an exception during node value parsing.
String with leading/trailing spaces or spaces within the value, e.g., ' (4 (2)(3)) '	Trim the entire string and handle potential spaces within value parsing or throw an exception.
Deeply nested tree structure, potentially causing stack overflow with recursive solutions	Consider an iterative approach using a stack to avoid recursion depth limits.
Integer overflow when parsing node values from the string	Use appropriate data types and error checking to handle potential overflow scenarios.