Introduction to Binary Trees

I/P: 50, 25, 12, null, null, 37, 30, null, null, null, 75, 62, null, 70, null, null, 87, null, null

O/P:

25 <- 50 -> 75

12 <- 25 -> 37

. <- 12 -> .

30 <- 37 -> .

. <- 30 -> .

62 <- 75 -> 87

. <- 62 -> 70

. <- 70 -> .

. <- 87 -> .

Construction Analysis:

Step 1. state = 1

                then, add left child to parent node

Step 2. state = 2

                then, add right child to parent node

Step 3. state = 3

                then, pop(), it means no further child to be added

package pep.Day31;

import java.util.Stack;

public class Intro_Binary_Trees {
    private static class Pair {
        Node node;
        int state;

        Pair(Node node, int state) {
            this.node = node;
            this.state = state;
        }
    }

    private 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 Node construct(Integer[] arr) {
        Stack<Pair> stack = new Stack<>();
        Node root = new Node(arr[0], null, null);
        Pair rootPair = new Pair(root, 1);
        stack.push(rootPair);

        int idx = 0;
        while (stack.size() > 0) {
            Pair top = stack.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);
                    stack.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);
                    stack.push(rp);
                } else {
                    top.node.right = null;
                }

                top.state++;
            } else {
                stack.pop();
            }
        }
        return root;
    }

    public static void display(Node node) {
        if (node == null)
            return;
        String str = "";
        str += node.left == null ? "." : node.left.data;
        str += " <- " + node.data + " -> ";
        str += node.right == null ? "." : node.right.data;

        System.out.println(str);
        display(node.left);
        display(node.right);
    }

    public static void main(String[] args) {
        Integer[] arr = {50, 25, 12, null, null, 37, 30, null, null, null,
                75, 62, null, 70, null, null, 87, null, null};

        Node root = construct(arr);
        display(root);
    }
}