Construct Binary Tree from String with bracket representation | Java program to cona binary tree from the given String ; A binary tree node has data , pointer to left child and a pointer to right child ; Helper function that allocates a new node ; This funtcion is here just to test ; function to return the index of close parenthesis ; Inbuilt stack ; if open parenthesis , push it ; if close parenthesis ; if stack is empty , this is the required index ; if not found return - 1 ; function to contree from String ; Base case ; new root ; if next char is ' ( ' find the index of its complement ' ) ' ; if index found ; call for left subtree ; call for right subtree ; Driver Code
import java . util . * ; class GFG { static class Node { int data ; Node left , right ; } ; static Node newNode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return ( node ) ; } static void preOrder ( Node node ) { if ( node == null ) return ; System . out . printf ( " % d ▁ " , node . data ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } static int findIndex ( String str , int si , int ei ) { if ( si > ei ) return - 1 ; Stack < Character > s = new Stack < > ( ) ; for ( int i = si ; i <= ei ; i ++ ) { if ( str . charAt ( i ) == ' ( ' ) s . add ( str . charAt ( i ) ) ; else if ( str . charAt ( i ) == ' ) ' ) { if ( s . peek ( ) == ' ( ' ) { s . pop ( ) ; if ( s . isEmpty ( ) ) return i ; } } } return - 1 ; } static Node treeFromString ( String str , int si , int ei ) { if ( si > ei ) return null ; Node root = newNode ( str . charAt ( si ) - '0' ) ; int index = - 1 ; if ( si + 1 <= ei && str . charAt ( si + 1 ) == ' ( ' ) index = findIndex ( str , si + 1 , ei ) ; if ( index != - 1 ) { root . left = treeFromString ( str , si + 2 , index - 1 ) ; root . right = treeFromString ( str , index + 2 , ei - 1 ) ; } return root ; } public static void main ( String [ ] args ) { String str = "4(2(3 ) ( 1 ) ) (6(5 ) ) " ; Node root = treeFromString ( str , 0 , str . length ( ) - 1 ) ; preOrder ( root ) ; } }