Tree-Traverse-Order-Level-Recursive

package treesample.levelorder.recursive;


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

class LevelOrderRecursive {
    Node root;

    public LevelOrderRecursive() { root = null; }

    void LevelOrder()
    {
        int h = height(root);
        int i;
        for (i=1; i<=h; i++)
            CurrentLevel(root, i);
    }
    int height(Node root) {
        if (root == null)
            return 0;
        else {
            int lheight = height(root.left);
            int rheight = height(root.right);
            if (lheight > rheight)
                return(lheight+1);
            else return(rheight+1);
        }
    }
    void CurrentLevel (Node root ,int level) {
        if (root == null){
            return;
        }
        if (level == 1){
            System.out.print(root.data + " ");
        }
        else if (level > 1) {
            CurrentLevel(root.left, level-1);
            CurrentLevel(root.right, level-1);
        }
    }
    public static void main(String args[])
    {
        LevelOrderRecursive tree = new LevelOrderRecursive();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        tree.LevelOrder();

    }
//There are basically two functions in this approach. 
// One of them is used to print all nodes at a particular level (CurrentLevel),
// and another is used to print level order traversal of the tree (Levelorder).
//
//In the CurrentLevel function, we find the height of the tree and call the LevelOrder 
// function for every level between 1 to height.
//In the LevelOrder function we pass two parameters level and root. we follow the below steps:
//First check if root is null then return.
//Check if level is equal to 1 then print the current root value.
//Now, call recursively call both the children of the current root with 
// decrementing the value of level by 1.
//Time complexity: For a skewed tree, time complexity will be O(n^2).
//Space complexity: For a skewed tree space complexity will be O(n) and for a
}