Construct a Binary Tree from String with bracket representation | Set 2

0 0 7 minutes read

Given a string s consisting of parentheses {‘(‘ and ‘)’} and integers, the task is to construct a Binary Tree from it and print its Preorder traversal.

Examples:

Input: S = “1(2)(3)”
Output: 1 2 3
Explanation: The corresponding binary tree is as follows:
1
/ \
2 3

Input: “4(2(3)(1))(6(5))”
Output: 4 2 3 1 6 5
Explanation:
The corresponding binary tree is as follows:

4
/ \
2 6
/ \ /
3 1 5

Recursive Approach: Refer to the previous article to solve the problem recursively.
Time Complexity: O(N²)
Auxiliary Space: O(N)

Approach: This problem can be solved using stack data structure. Follow the steps below to solve the problem:

Update the character at position 0 as root of the binary tree and initialize a stack stk.
Iterate in the range [1, N-1] using the variable i:
- If ‘(‘ is encountered, push the root to the stack stk.
- Otherwise, if ‘)’ is encountered update root as the topmost element of the stack and pop the topmost element.
- Otherwise, if the character is a number, then, branch into the part that is null (left or right).
At the end of the above steps, return the root node of the binary tree.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Build a tree node having left and
// right pointers set to null initially
struct Node {
    Node* left;
    Node* right;
    int data;
 
    // Constructor to set the data of
    // the newly created tree node
    Node(int element)
    {
        data = element;
        this->left = nullptr;
        this->right = nullptr;
    }
};
 
// Utility function to print
// preorder traversal of the tree
void preorder(Node* root)
{
    if (!root)
        return;
 
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}
 
// Function to construct a
// tree using bracket notation
Node* constructTree(string s)
{
 
    // First character is the root of the tree
    Node* root = new Node(s[0] - '0');
 
    // Stack used to store the
    // previous root elements
    stack<Node*> stk;
 
    // Iterate over remaining characters
    for (int i = 1; i < s.length(); i++) {
 
        // If current character is '('
        if (s[i] == '(') {
 
            // Push root into stack
            stk.push(root);
        }
 
        // If current character is ')'
        else if (s[i] == ')') {
 
            // Make root the top most
            // element in the stack
            root = stk.top();
 
            // Remove the top node
            stk.pop();
        }
 
        // If current character is a number
        else {
 
            // If left is null, then put the new
            // node to the left and move to the
            // left of the root
            if (root->left == nullptr) {
 
                Node* left = new Node(s[i] - '0');
                root->left = left;
                root = root->left;
            }
 
            // Otherwise, if right is null, then
            // put the new node to the right and
            // move to the right of the root
            else if (root->right == nullptr) {
 
                Node* right = new Node(s[i] - '0');
                root->right = right;
                root = root->right;
            }
        }
    }
 
    // Return the root
    return root;
}
 
// Driver code
int main()
{
    // Input
    string s = "4(2(3)(1))(6(5))";
 
    // Function calls
    Node* root = constructTree(s);
    preorder(root);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class Main
{
    // Class containing left and
    // right child of current
    // node and key value
    static class Node {
        
        public int data;
        public Node left, right;
        
        public Node(int element)
        {
            data = element;
            left = right = null;
        }
    }
     
    // Utility function to print
    // preorder traversal of the tree
    static void preorder(Node root)
    {
        if (root == null)
            return;
       
        System.out.print(root.data + " ");
        preorder(root.left);
        preorder(root.right);
    }
       
    // Function to construct a
    // tree using bracket notation
    static Node constructTree(String s)
    {
       
        // First character is the root of the tree
        Node root = new Node(s.charAt(0) - '0');
       
        // Stack used to store the
        // previous root elements
        Stack<Node> stk = new Stack<Node>();
       
        // Iterate over remaining characters
        for (int i = 1; i < s.length(); i++) {
       
            // If current character is '('
            if (s.charAt(i) == '(') {
       
                // Push root into stack
                stk.push(root);
            }
       
            // If current character is ')'
            else if (s.charAt(i) == ')') {
       
                // Make root the top most
                // element in the stack
                root = stk.peek();
       
                // Remove the top node
                stk.pop();
            }
       
            // If current character is a number
            else {
       
                // If left is null, then put the new
                // node to the left and move to the
                // left of the root
                if (root.left == null) {
       
                    Node left = new Node(s.charAt(i) - '0');
                    root.left = left;
                    root = root.left;
                }
       
                // Otherwise, if right is null, then
                // put the new node to the right and
                // move to the right of the root
                else if (root.right == null) {
       
                    Node right = new Node(s.charAt(i) - '0');
                    root.right = right;
                    root = root.right;
                }
            }
        }
       
        // Return the root
        return root;
    }
     
    public static void main(String[] args) {
        // Input
        String s = "4(2(3)(1))(6(5))";
       
        // Function calls
        Node root = constructTree(s);
        preorder(root);
    }
}
 
// This code is contributed by divyesh072019.

Python3

# Python program for the above approach
 
# Build a tree node having left and
# right pointers set to null initially
class Node:
    # Constructor to set the data of
    # the newly created tree node
    def __init__(self, element):
        self.data = element
        self.left = None
        self.right = None
 
# Utility function to print
# preorder traversal of the tree
def preorder(root):
    if (not root):
        return
 
    print(root.data, end = " ")
    preorder(root.left)
    preorder(root.right)
 
# Function to construct a
# tree using bracket notation
def constructTree(s):
 
    # First character is the root of the tree
    root = Node(ord(s[0]) - ord('0'))
 
    # Stack used to store the
    # previous root elements
    stk = []
 
    # Iterate over remaining characters
    for i in range(1,len(s)):
        # If current character is '('
        if (s[i] == '('):
 
            # Push root into stack
            stk.append(root)
 
        # If current character is ')'
        elif (s[i] == ')'):
 
            # Make root the top most
            # element in the stack
            root = stk[-1]
 
            # Remove the top node
            del stk[-1]
        # If current character is a number
        else:
 
            # If left is null, then put the new
            # node to the left and move to the
            # left of the root
            if (root.left == None):
 
                left = Node(ord(s[i]) - ord('0'))
                root.left = left
                root = root.left
 
            # Otherwise, if right is null, then
            # put the new node to the right and
            # move to the right of the root
            elif (root.right == None):
 
                right =  Node(ord(s[i]) - ord('0'))
                root.right = right
                root = root.right
 
    # Return the root
    return root
 
# Driver code
if __name__ == '__main__':
    # Input
    s = "4(2(3)(1))(6(5))"
 
    # Function calls
    root = constructTree(s)
    preorder(root)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG
{
     
    // Class containing left and
    // right child of current
    // node and key value
    class Node {
       
        public int data;
        public Node left, right;
       
        public Node(int element)
        {
            data = element;
            left = right = null;
        }
    }
     
    // Utility function to print
    // preorder traversal of the tree
    static void preorder(Node root)
    {
        if (root == null)
            return;
      
        Console.Write(root.data + " ");
        preorder(root.left);
        preorder(root.right);
    }
      
    // Function to construct a
    // tree using bracket notation
    static Node constructTree(string s)
    {
      
        // First character is the root of the tree
        Node root = new Node(s[0] - '0');
      
        // Stack used to store the
        // previous root elements
        Stack stk = new Stack();
      
        // Iterate over remaining characters
        for (int i = 1; i < s.Length; i++) {
      
            // If current character is '('
            if (s[i] == '(') {
      
                // Push root into stack
                stk.Push(root);
            }
      
            // If current character is ')'
            else if (s[i] == ')') {
      
                // Make root the top most
                // element in the stack
                root = (Node)(stk.Peek());
      
                // Remove the top node
                stk.Pop();
            }
      
            // If current character is a number
            else {
      
                // If left is null, then put the new
                // node to the left and move to the
                // left of the root
                if (root.left == null) {
      
                    Node left = new Node(s[i] - '0');
                    root.left = left;
                    root = root.left;
                }
      
                // Otherwise, if right is null, then
                // put the new node to the right and
                // move to the right of the root
                else if (root.right == null) {
      
                    Node right = new Node(s[i] - '0');
                    root.right = right;
                    root = root.right;
                }
            }
        }
      
        // Return the root
        return root;
    }
 
  // Driver code
  static void Main()
  {
     
    // Input
    string s = "4(2(3)(1))(6(5))";
  
    // Function calls
    Node root = constructTree(s);
    preorder(root);
  }
}
 
// This code is contributed by decode2207.

Javascript

<script>
    // Javascript program for the above approach   
    class Node
    {
        constructor(element) {
           this.left = null;
           this.right = null;
           this.data = element;
        }
    }
     
    // Utility function to print
    // preorder traversal of the tree
    function preorder(root)
    {
        if (root == null)
            return;
 
        document.write(root.data + " ");
        preorder(root.left);
        preorder(root.right);
    }
 
    // Function to construct a
    // tree using bracket notation
    function constructTree(s)
    {
 
        // First character is the root of the tree
        let root = new Node(s[0].charCodeAt() - '0'.charCodeAt());
 
        // Stack used to store the
        // previous root elements
        let stk = [];
 
        // Iterate over remaining characters
        for (let i = 1; i < s.length; i++) {
 
            // If current character is '('
            if (s[i] == '(') {
 
                // Push root into stack
                stk.push(root);
            }
 
            // If current character is ')'
            else if (s[i] == ')') {
 
                // Make root the top most
                // element in the stack
                root = stk[stk.length - 1];
 
                // Remove the top node
                stk.pop();
            }
 
            // If current character is a number
            else {
 
                // If left is null, then put the new
                // node to the left and move to the
                // left of the root
                if (root.left == null) {
 
                    let left = new Node(s[i].charCodeAt() - '0'.charCodeAt());
                    root.left = left;
                    root = root.left;
                }
 
                // Otherwise, if right is null, then
                // put the new node to the right and
                // move to the right of the root
                else if (root.right == null) {
 
                    let right = new Node(s[i].charCodeAt() - '0'.charCodeAt());
                    root.right = right;
                    root = root.right;
                }
            }
        }
 
        // Return the root
        return root;
    }
     
    // Input
    let s = "4(2(3)(1))(6(5))";
  
    // Function calls
    let root = constructTree(s);
    preorder(root);
 
// This code is contributed by divyeshrabadiya07.
</script>

Output:

4 2 3 1 6 5

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!