Construct Binary Tree from String with bracket representation | Helper class 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 conStruct tree 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
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def preOrder ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT print ( node . data , end = " ▁ " ) NEW_LINE preOrder ( node . left ) NEW_LINE preOrder ( node . right ) NEW_LINE DEDENT def findIndex ( Str , si , ei ) : NEW_LINE INDENT if ( si > ei ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT s = [ ] NEW_LINE for i in range ( si , ei + 1 ) : NEW_LINE INDENT if ( Str [ i ] == ' ( ' ) : NEW_LINE INDENT s . append ( Str [ i ] ) NEW_LINE DEDENT elif ( Str [ i ] == ' ) ' ) : NEW_LINE INDENT if ( s [ - 1 ] == ' ( ' ) : NEW_LINE INDENT s . pop ( - 1 ) NEW_LINE if len ( s ) == 0 : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT DEDENT DEDENT return - 1 NEW_LINE DEDENT def treeFromString ( Str , si , ei ) : NEW_LINE INDENT if ( si > ei ) : NEW_LINE INDENT return None NEW_LINE DEDENT root = newNode ( ord ( Str [ si ] ) - ord ( '0' ) ) NEW_LINE index = - 1 NEW_LINE if ( si + 1 <= ei and Str [ si + 1 ] == ' ( ' ) : NEW_LINE INDENT index = findIndex ( Str , si + 1 , ei ) NEW_LINE DEDENT if ( index != - 1 ) : NEW_LINE INDENT root . left = treeFromString ( Str , si + 2 , index - 1 ) NEW_LINE root . right = treeFromString ( Str , index + 2 , ei - 1 ) NEW_LINE DEDENT return root NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT Str = "4(2(3 ) ( 1 ) ) (6(5 ) ) " NEW_LINE root = treeFromString ( Str , 0 , len ( Str ) - 1 ) NEW_LINE preOrder ( root ) NEW_LINE DEDENT