LeetCode 536: Construct Binary Tree from String Solution

Master LeetCode problem 536 (Construct Binary Tree from String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

536. Construct Binary Tree from String

Medium

String Stack Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

Given a string representing a binary tree, we need to construct the binary tree from this string.

We can solve this problem using a recursive approach. We will start by parsing the string to extract the root value and construct the root node. Then, we will recursively construct the left and right subtrees by identifying their respective strings from the input string.

Example:

Input: "4(2(3)(1))(6(5))" Output: A binary tree representing the input string.

Algorithm:

Start by creating a helper function that takes a string and a start index as input.
Extract the root value from the string at the start index.
Create the root node with the extracted value.
Check if there are left and right children for the current node.
If there is a left child, recursively call the helper function with the substring representing the left child.
If there is a right child, recursively call the helper function with the substring representing the right child.
Return the constructed root node.
Finally, call the helper function with the input string starting from index 0.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input string, as we traverse the string only once.

Space Complexity:

The space complexity is also O(n) due to the recursive calls and the space used by the call stack.

Solution Code

class Solution {
    public TreeNode str2tree(String s) {
        if (s.isEmpty()) {
            return null;
        }
        return helper(s, 0);
    }
    
    private TreeNode helper(String s, int start) {
        int end = start;
        while (end < s.length() && (Character.isDigit(s.charAt(end)) || s.charAt(end) == '-')) {
            end++;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(s.substring(start, end)));
        
        if (end < s.length() && s.charAt(end) == '(') {
            int count = 1;
            int i = end + 1;
            while (count != 0) {
                if (s.charAt(i) == '(') {
                    count++;
                } else if (s.charAt(i) == ')') {
                    count--;
                }
                i++;
            }
            root.left = helper(s, end + 1);
            root.right = helper(s, i);
        }
        
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 536 (Construct Binary Tree from String)?

This page provides optimized solutions for LeetCode problem 536 (Construct Binary Tree from String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 536 (Construct Binary Tree from String)?

The time complexity for LeetCode 536 (Construct Binary Tree from String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 536 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 536 in Java, C++, or Python.

Back to LeetCode Solutions