//Boundary Traversal of a Binary Tree
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

void leftBoundary(Node* node, vector<int>& res) {
    if (!node || (!node->left && !node->right)) return;
    res.push_back(node->val);
    if (node->left) leftBoundary(node->left, res);
    else leftBoundary(node->right, res);
}

void leaves(Node* node, vector<int>& res) {
    if (!node) return;
    if (!node->left && !node->right) res.push_back(node->val);
    leaves(node->left, res);
    leaves(node->right, res);
}

void rightBoundary(Node* node, vector<int>& res) {
    if (!node || (!node->left && !node->right)) return;
    if (node->right) rightBoundary(node->right, res);
    else rightBoundary(node->left, res);
    res.push_back(node->val);
}

vector<int> boundaryTraversal(Node* root) {
    vector<int> res;
    if (!root) return res;
    res.push_back(root->val);
    leftBoundary(root->left, res);
    leaves(root->left, res);
    leaves(root->right, res);
    rightBoundary(root->right, res);
    return res;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    vector<int> res = boundaryTraversal(root);
    for (int x : res) cout << x << " ";
    return 0;
}