Data-Structures---Algorithms/Constructing A Binary Tree at main · uditbhaskar21/Data-Structures---Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class constructingAbt {
    public static class Node{
        int data;
        Node left;
        Node right;
        Node(int data,Node left,Node right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    public static class Pair{
        Node node;
        int state;
        Pair(Node node,int state){
            this.node = node;
            this.state = state;
        }
    }
    public static void main(String[] args)throws Exception {
        Integer[] arr = {50,25,12,null,null,37,30,null,null,null,75,62,null,70,null,null,80,null,null};

        Node root = new Node(arr[0],null,null );
        Pair p= new Pair(root,1);

        Stack<Pair> st = new Stack<>();
        st.push(p);

        int idx = 0;

        while (st.size()>0){
            Pair top = st.peek();
            if (top.state == 1){
                idx++;
                if (arr[idx]!=null){
                    top.node.left = new Node(arr[idx],null,null );
                    Pair lp = new Pair(top.node.left, 1);
                    st.push(lp);
                }else {
                    top.node.left = null;
                }
                top.state++;
            }
            else if(top.state == 2){
                idx++;
                if(arr[idx]!=null){
                    top.node.right= new Node(arr[idx],null,null );
                    Pair rp = new Pair(top.node.right, 1);
                    st.push(rp);
                }else {
                    top.node.right = null;
                }
                top.state++;
            }
            else if(top.state == 3){
                st.pop();
            }
        }
    }
}