package com.imdevil.JobInterview;

import java.util.Stack;

public class BtTree{
    
    static class Node{
        char data;
        Node lchild;
        Node rchild;
        public Node() {
            
        }
        public Node(char data,Node lchild,Node rchild){
            this.data = data;
            this.lchild = lchild;
            this.rchild = rchild;
        }
    }
    
    public Node createBtTree(String str){
        Stack<Node> stack = new Stack<>();
        Node bt = null;
        Node node = null;
        int k = 0;
        for(int i=0;i<str.length();i++){
            if (str.charAt(i) >= 'A' && str.charAt(i) <= 'z') {
                node = new Node();
                node.data = str.charAt(i);
                node.lchild = null;
                node.rchild = null;
                if (bt == null) {
                    bt =  node;
                }else {
                    switch (k) {
                    case 1:
                        stack.peek().lchild = node;
                        break;
                    case 2:
                        stack.peek().rchild = node;
                        break;
                    default:
                        break;
                    }
                }
            }else if(str.charAt(i) == '(') {
                stack.push(node);
                k = 1;
            }else if(str.charAt(i) == ')'){
                stack.pop();
            }else if (str.charAt(i) == ',') {
                k = 2;
            }
        }
        return bt;
    }

    public int depth(Node bt){
        if (bt == null) {
            return 0;
        }
        int left = depth(bt.lchild);
        int right = depth(bt.rchild);
        return Math.max(left, right)+1;
    }
    
    public void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data);
            preOrder(node.lchild);
            preOrder(node.rchild);
        }
    }
    
    public void midOrder(Node node){
        if (node != null) {
            midOrder(node.lchild);
            System.out.print(node.data);
            midOrder(node.rchild);
        }
    }
    
    public void postOrder(Node node){
        if (node != null) {
            postOrder(node.lchild);
            postOrder(node.rchild);
            System.out.print(node.data);
        }
    }
    
    public void dispLeaf(Node node){
        if (node != null) {
            if (node.lchild == null && node.rchild == null) {
                System.out.print(node.data);
            }
            dispLeaf(node.lchild);
            dispLeaf(node.rchild);
        }
    }
    
    public static void main(String[] args) {
        String str = "A(B(D(,G),)C(E,F))";
        BtTree tree = new BtTree();
        Node node = tree.createBtTree(str);
        System.out.println(tree.depth(node));   --->4
        tree.preOrder(node); --->ABDGCEF
        System.out.println();
        tree.midOrder(node); --->DGBAECF
        System.out.println();
        tree.postOrder(node); ---->GDBEFCA
        System.out.println();
        tree.dispLeaf(node);  --->GEF
    }
    
}