package com.bitree;
import java.util.*;

public class BiTree {
    public BiTree(){
        Node node6 = new Node(6, null, null);
        Node node7 = new Node(7, null, null);
        Node node5 = new Node(5, node6, node7);
        Node node4 = new Node(4, null, node5);
        Node node3 = new Node(3, null, null);
        Node node2 = new Node(2, node4, null);
        this.root = new Node(1, node2, node3);
    }
    
    public void PreOrder(){
        Stack<Node> s = new Stack<Node>();
        s.push(this.root);
        while (!s.isEmpty())
        {
            Node node = s.pop();
            System.out.print(node.getItem());
            if (node.getRightChild() != null){
                s.push(node.getRightChild());
            }
            if (node.getLeftChild() != null){
                s.push(node.getLeftChild());
            }
        }
    }
    public void InOrder(){
        Stack<Node> s= new Stack<Node>();
        Node node = this.root;
        while (node != null || !s.isEmpty()){
            while (node != null){
                s.push(node);
                node = node.getLeftChild();
            }
            
            if (!s.isEmpty()){
                node = s.pop();
                System.out.print(node.getItem());
                node = node.getRightChild();
            }
        }
    }
    public void PostOrder(){
        Stack<Node> s = new Stack<Node>();
        Stack<Node> sPre = new Stack<Node>();
        Node node = this.root;
        Node nodePrev = null;
        while (node != null || !s.isEmpty()){
            while (node != null){
                s.push(node);
                node = node.getLeftChild();
            }
            
            if (!s.isEmpty()){
                node = s.peek();
                if (!sPre.isEmpty())
                {
                    nodePrev = sPre.peek();
                    if (nodePrev == node)
                        sPre.pop();
                }
                if (node.getRightChild() == null || node == nodePrev){
                    node = s.pop();
                    System.out.print(node.getItem());
                    node = null;
                }
                else{
                    sPre.push(node);
                    node = node.getRightChild();
                }
            }
        }
    }
    
    private Node root;
    
    private class Node{
        public Node(int n, Node lNode, Node rNode){
            this.makeNode(n, lNode, rNode);
        }
        public void makeNode(int n, Node lNode, Node rNode){
            this.leftChild = lNode;
            this.rightChild = rNode;
            this.nItem = n;
        }
        public Node getLeftChild(){
            return this.leftChild;
        }
        public Node getRightChild(){
            return this.rightChild;
        }
        public int getItem(){
            return this.nItem;
        }
        private int nItem;
        private Node leftChild;
        private Node rightChild;
    }
}