Construct Binary Tree from String with Bracket Representation

Slug: construct-binary-tree-from-string-with-bracket-representation

Difficulty: Medium

Id: 710350

Topic Tags: Strings, Tree, Data Structures

Company Tags: None

Summary

Construct a binary tree from a given string representation using brackets. The input string is in the format of a pre-order traversal of the binary tree, where each node is represented as an integer followed by its left and right child nodes enclosed in square brackets. For example, "1[2[4]3[5[6]]]" represents the following binary tree:

Detailed Explanation

The problem requires constructing a binary tree from a string representation using brackets. The input string is in pre-order traversal format, where each node's value is followed by its left and right child nodes enclosed in square brackets.

To solve this problem, we can use a recursive approach to construct the binary tree. Here are the steps:

Initialize an empty binary tree.
Iterate through the input string. When you encounter an integer, create a new node with that value and add it to the current node's left or right child position (depending on whether it is a left or right bracket).
When you encounter a bracket, recursively construct the left subtree if it's an opening bracket ( '[' ) or the right subtree if it's a closing bracket ( ']' ).
Continue this process until the end of the input string.

Here's a step-by-step breakdown:

    Input String: "1[2[4]3[5[6]]]"
    1. Initialize an empty binary tree.
    2. Encounter "1", create a new node with value 1 and add it to the root of the binary tree.
    3. Encounter "[", recursively construct the left subtree.
        * Encounter "2", create a new node with value 2 and add it as the left child of the current node (node 1).
        * Encounter "[", recursively construct the left subtree of node 2.
            - Encounter "4", create a new node with value 4 and add it as the left child of node 2.
        * Encounter "]", return to the previous level and continue constructing the right subtree of node 1.
    4. Continue this process until the end of the input string, resulting in the constructed binary tree:

The time complexity of this solution is O(n), where n is the length of the input string, since we iterate through the string once to construct the binary tree. The space complexity is O(h), where h is the height of the binary tree, since we recursively construct the tree and store nodes in memory.

Optimized Solutions

Java

View GeeksforGeeks Problem

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode stringToTreeNode(String s) {
        if (s == null || s.length() == 0) return null;

        String[] nodes = s.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        constructTree(root, nodes, 1);
        return root;
    }

    private void constructTree(TreeNode node, String[] nodes, int index) {
        if (index >= nodes.length) return;

        String current = nodes[index];
        if (current.startsWith("[")) {
            // Left subtree
            node.left = new TreeNode(Integer.parseInt(current.substring(1, current.indexOf("]"))));
            constructTree(node.left, nodes, index + 1);
        } else if (current.endsWith("]")) {
            // Right subtree
            node.right = new TreeNode(Integer.parseInt(current.substring(0, current.length() - 1)));
            constructTree(node.right, nodes, index + 1);
        }
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.