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 3Input: “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(N2)
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:
- 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 initiallystruct 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 treevoid preorder(Node* root){ if (!root) return; cout << root->data << " "; preorder(root->left); preorder(root->right);}// Function to construct a// tree using bracket notationNode* 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 codeint 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 approachimport 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 initiallyclass 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 treedef preorder(root): if (not root): return print(root.data, end = " ") preorder(root.left) preorder(root.right)# Function to construct a# tree using bracket notationdef 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 codeif __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 approachusing 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
