package trees;

import java.util.Stack;

public class PrintTreePerimeter {


    /*
     * Given the root node of a binary tree, print nodes forming the boundary (perimeter).
     *
     *
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * O(h)
     *
     * Print the root node.
     * Print the left boundary in top-down order.
     * Print the leaf nodes in left-right order.
     * Print the right boundary in bottom-up order.
     * Push node values in a stack here. Once the leaf node is hit, pop all elements of the stack
     * while printing them.
     *
     * */


    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;

    protected static void printLeftPerimeter(Node root) {
        while (root != null) {

            int curr_val = root.data;

            if (root.left != null) {
                root = root.left;
                
            } else if (root.right != null) {
                root = root.right;
                
            } else {
                break;
            }
            
            System.out.print(curr_val + " ");
        }
    }
    

    public static void printRightPerimeter(Node root) {

        Stack<Integer> rightValues = new Stack<>();
        
        while (root != null) {

            int curr_val = root.data;

            if (root.right != null) {
                root = root.right;
                
            } else if (root.left != null) {
                root = root.left;
                
            } else {
                break; // leaf node.
            }

            rightValues.push(curr_val);
        }

        while (!rightValues.isEmpty()) {
            System.out.print(rightValues.pop() + " ");
        }
    }
    
    

    protected static void printLeafNodes(Node root) {
        if (root != null) {
            printLeafNodes(root.left);
            printLeafNodes(root.right);

            if (root.left == null &&
                    root.right == null) {
                System.out.print(root.data + " ");
            }
        }
    }
    

    protected static void displayTreePerimeter(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");

            printLeftPerimeter(root.left);

            if (root.left != null || root.right != null) {
                printLeafNodes(root);
            }

            printRightPerimeter(root.right);
        }
    }
    

    public static void main(String[] argv) {
        PrintTreePerimeter printTreePerimeter = new PrintTreePerimeter();
        printTreePerimeter.root1 = new Node(1);
        printTreePerimeter.root1.left = new Node(2);
        printTreePerimeter.root1.right = new Node(3);
        printTreePerimeter.root1.left.left = new Node(4);
        printTreePerimeter.root1.left.right = new Node(5);
        printTreePerimeter.root1.right.left = new Node(6);
        printTreePerimeter.root1.right.right = new Node(7);
        
        System.out.print("Perimeter:\n");
        displayTreePerimeter(printTreePerimeter.root1);
    }
}