Problem Statement

Given a root of Binary Tree, perform the boundary traversal of the tree.

The boundary traversal is the process of visiting the boundary nodes of the binary tree in the anticlockwise direction, starting from the root.

Examples

Example 1:

Input: root = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9]
Output: [1, 2, 4, 8, 9, 6, 7, 3]

Example 2:

Input : root = [1, 2, null, 4, 9, 6, 5, 3, null, null, null, null, null, 7, 8]
Output : [1, 2, 4, 6, 5, 7, 8]

Different Approaches

1️⃣ Anti-Clock Wise

Intuition:

The boundary traversal algorithm aims to traverse the boundary of a binary tree in an anti-clockwise direction. The traversal is divided into three main parts: the left boundary, the bottom boundary (leaf nodes), and the right boundary. The left boundary traversal starts from the root and moves to the leftmost child, switching to the right child if the left is unavailable, until reaching a leaf node. The bottom boundary includes all leaf nodes using a simple preorder traversal. The right boundary traversal is similar to the left boundary but in the reverse direction, moving from the root to the rightmost child, and reversing the order of nodes in the result.

Code:

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
public:
    // Function to check if a node is a leaf
    bool isLeaf(TreeNode* root) {
        return !root->left && !root->right;
    }

    // Function to add the left boundary of the tree
    void addLeftBoundary(TreeNode* root, vector<int>& res) {
        TreeNode* curr = root->left;
        while (curr) {
            if (!isLeaf(curr)) {
                res.push_back(curr->data);
            }
            if (curr->left) {
                curr = curr->left;
            } else {
                curr = curr->right;
            }
        }
    }

    // Function to add the right boundary of the tree
    void addRightBoundary(TreeNode* root, vector<int>& res) {
        TreeNode* curr = root->right;
        vector<int> temp;
        while (curr) {
            if (!isLeaf(curr)) {
                temp.push_back(curr->data);
            }
            if (curr->right) {
                curr = curr->right;
            } else {
                curr = curr->left;
            }
        }
        for (int i = temp.size() - 1; i >= 0; --i) {
            res.push_back(temp[i]);
        }
    }

    // Function to add the leaves of the tree
    void addLeaves(TreeNode* root, vector<int>& res) {
        if (isLeaf(root)) {
            res.push_back(root->data);
            return;
        }
        if (root->left) {
            addLeaves(root->left, res);
        }
        if (root->right) {
            addLeaves(root->right, res);
        }
    }

    // Main function to perform the boundary traversal of the binary tree
    vector<int> boundary(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        if (!isLeaf(root)) {
            res.push_back(root->data);
        }

        addLeftBoundary(root, res);
        addLeaves(root, res);
        addRightBoundary(root, res);

        return res;
    }
};

// Helper function to print the result
void printResult(const vector<int>& result) {
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    Solution solution;

    // Get the boundary traversal
    vector<int> result = solution.boundary(root);

    // Print the result
    cout << "Boundary Traversal: ";
    printResult(result);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) where N is the number of nodes in the Binary Tree. This is due to traversing the left boundary, bottom nodes, and right boundary sequentially, each operation being at most O(N).
• Space Complexity: O(N) for storing boundary nodes and auxiliary recursion stack space in the worst-case scenario of a skewed tree.