Converting Specific kind of String to Binary Tree

Question

We have an input string in this format "(1(2(4)(5))(3(6(8)(9))(7)))"
We have to build a Binary Tree such that 1 is the root node and the first complete bracket contains (2(4)(5)) contains the family of 1's left child
and (3(6(8)(9))(7)) is the family of the right child of the root A.
Finally the tree will look like this.
Like this

I am not able to find the exact algorithm to write convert this one. Thanks in Advance!

Answer 1

Think Stack. When you see a "(" push the element onto the stack, when you see a ")" pop the stack, but assign it as a child to the top element of the stack.

So lets go through the example "( 1 ( 2 ( 4 ) ( 5 ) ) ( 3 ( 6 ( 8 ) ( 9 ) ) ( 7 ) ) )"

• (1 -> push 1

• (2 -> push 2

• (4 -> push 4

• ) -> pop 4, but assign 4 as child to top of stack which is 2 ( see if left is available then assign as left child otherwise right child )

Current tree :

• (5 -> push 5
• ) -> pop 5, top of the stack is still 2 ( left is not available so assign it as right child of 2 )

Current tree:

• ) -> pop 2, top of the stack is 1 ( left of 1 is available, so assign 2 as left child of 1)

Current tree:

• (3 -> push 3

• (6 -> push 6

• (8 -> push 8

• ) -> pop 8, top of the stack 6's left is available assign 8 as left of 6

Current tree:

• (9 -> push 9

• ) -> pop 9 -> add it to top of stack's right child i.e. 6's right child because 6's left is taken as 8.

Current tree:

• ) -> pop 6 -> add it to top of stack i.e. 3's left child as it is available.

Current tree:

• (7 -> push 7

• ) -> pop 7 -> add it to top of stack i.e. 3's right child because 3's left child is taken as 6.

• ) -> pop 3 -> add it to top of stack i.e. 1's right child because 1's left child is taken as 2.

Current tree:

• ) -> pop 1 -> there is nothing in the stack now. Done.

Complete runnable example in Java with implementation using a stack is:

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        TreeNode root = buildTree("(1(2(4)(5))(3(6(8)(9))(7)))");
        levelOrder(root);
    }
    
    static class TreeNode {
        int val;
        TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    
    private static TreeNode buildTree(String s) {
        Deque<TreeNode> dq = new ArrayDeque<>();
        TreeNode rootNode = null;
        for ( int i = 0; i < s.length(); i++ ) {
            if ( s.charAt(i) == '(' ) {
                Integer current = Integer.parseInt(String.valueOf(s.charAt(i+1)));
                dq.push(new TreeNode(current));
            } else if ( s.charAt(i) == ')' ) {
                TreeNode node = dq.pop();
                if ( dq.isEmpty() ) {
                    break;
                } else {
                    
                    rootNode = dq.peek();
                    if (rootNode.left == null) {
                        rootNode.left = node;
                    } else {
                        rootNode.right = node;
                    }
                }
            }
        }
        return rootNode;
    }
    
    private static void levelOrder(TreeNode root) {
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.offer(root);
        while(!dq.isEmpty()) {
            int sz = dq.size();
            
            for ( int i = 0; i < sz; i++ ) {
                TreeNode node = dq.poll();
                System.out.print(node.val + " ");
                if ( node.left != null ) {
                    dq.offer(node.left);
                }
                if ( node.right != null ) {
                    dq.offer(node.right);
                }
            }
            System.out.println();
        }
        
    }

}