// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/* BEGIN */

#include <cstdio>

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return new TreeNode(val); // "new" to avoid freeing memory
        }
        if (val <= root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

/* END */

#include <queue>

using std::queue;

void print_tree(TreeNode *root) {
    if (root == nullptr) {
        printf("null\n");
        return;
    }
    queue<TreeNode *> q;
    q.push(root);
    TreeNode *curr = nullptr;
    int cnt = q.size();
    while (q.size() != 0) {
        curr = q.front();
        q.pop();
        cnt--;
        printf("%d ", curr->val);
        if (curr->left != nullptr) {
            q.push(curr->left);
        }
        if (curr->right != nullptr) {
            q.push(curr->right);
        }
        if (cnt == 0) {
            cnt = q.size();
            printf("\n");
        }
    }
}

int main() {
    TreeNode n1(1), n2(2), n3(3), n4(4), n7(7);
    n2.left = &n1;
    n2.right = &n3;
    n4.left = &n2;
    n4.right = &n7;
    TreeNode *root = &n4;
    print_tree(root);
    root = (new Solution())->insertIntoBST(root, 5);
    print_tree(root);
}