#pragma once
#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

struct tree
{
    int inf;
    tree *left;
    tree *right;
    tree *parent;
};

tree *node(int x)
{
    tree *n = new tree;
    n->inf = x;
    n->parent = NULL;
    n->right = NULL;
    n->left = NULL;
    return n;
}

void find(tree *&tr, int x, tree *&res)
{
    if (tr)
    {
        if (tr->inf == x)
        {
            res = tr;
        }
        else
        {
            find(tr->left, x, res);
            find(tr->right, x, res);
        }
    }
}

void print(tree *tr, int k)
{
    if (!tr) cout << "Empty tree" << endl;
    else
    {
        queue<tree*> cur, next;
        tree *r = tr;
        cur.push(r);
        int j = 0;
        while (cur.size())
        {
            if (j == 0)
            {
                for (int i = 0; i < (int) pow(2.0, k) - 1; i++)
                    cout << ' ';
            }
            tree *buf = cur.front();
            cur.pop();
            j++;
            if (buf)
            {
                cout << buf->inf;
                next.push(buf->left);
                next.push(buf->right);
                for (int i = 0; i < (int) pow(2.0, k + 1) - 1; i++)
                    cout << ' ';
            }
            if (!buf)
            {
                for (int i = 0; i < (int) pow(2.0, k + 1) - 1; i++)
                    cout << ' ';
                cout << ' ';
            }
            if (cur.empty())
            {
                cout << endl;
                swap(cur, next);
                j = 0;
                k--;
            }
        }
    }
}