Boundary Traversal of Binary Tree

Problem link - Boundary Traversal

You are given a binary tree having 'n' nodes.

The boundary nodes of a binary tree include the nodes from the left and right boundaries and the leaf nodes, each node considered once.

Figure out the boundary nodes of this binary tree in an Anti-Clockwise direction starting from the root node.

Intuition

• Divide the problem into 3 parts
• one is printing the left side of boundary without leaves from top to bottom
• second printing the leaves of tree from left to right
• third printing the right side of boundary without leaves from bottom to top (Note: we are printing leaves seperately,so we avoid printing them in side)

Approach

Start with the Root:
Print or store the root node's value first since it is the starting point of the traversal.

Left Boundary:

• Create a function leftBoundary that:
• Adds the current node's value to the result list.
• Recursively explores the left child first.
• If there is no left child, it will explore the right child instead.
• This ensures that leaf nodes are not included in this part of the traversal.

Leaves:
Create a function leaves that:
Recursively traverses both left and right subtrees.
Adds a node’s value to the result list if it is a leaf (i.e., has no left or right children).

Right Boundary:

• Create a function rightBoundary that:
• Recursively explores the right child first.
• If there is no right child, it will explore the left child.
• The node’s value is added to the result list after the recursive calls to ensure the right boundary is collected in bottom-up order.

Code

#include <vector>

template <typename T>
class TreeNode {
public:
    T data;
    TreeNode<T>* left;
    TreeNode<T>* right;

    TreeNode(T data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }

    ~TreeNode() {
        if (left)
            delete left;
        if (right)
            delete right;
    }
};

void leftBoundary(TreeNode<int>* root, std::vector<int>& ans) {
    if (root == NULL) {
        return;
    }
    if (root->left || root->right) { // Ignore leaves
        ans.push_back(root->data);
    }
    if (root->left) {
        leftBoundary(root->left, ans);
    } else if (root->right) {
        leftBoundary(root->right, ans);
    }
}

void rightBoundary(TreeNode<int>* root, std::vector<int>& ans) {
    if (root == NULL) {
        return;
    }
    if (root->right || root->left) { // Ignore leaves
        if (root->right) {
            rightBoundary(root->right, ans);
        } else {
            rightBoundary(root->left, ans);
        }
        ans.push_back(root->data);
    }
}

void leaves(TreeNode<int>* root, std::vector<int>& ans) {
    if (root == NULL) {
        return;
    }
    if (!root->left && !root->right) {
        ans.push_back(root->data);
    }
    leaves(root->left, ans);
    leaves(root->right, ans);
}

std::vector<int> traverseBoundary(TreeNode<int>* root) {
    std::vector<int> ans;
    if (root == NULL) {
        return ans; // Return empty vector for null root
    }
    ans.push_back(root->data); // Add root node
    leftBoundary(root->left, ans); // Collect left boundary
    leaves(root, ans); // Collect leaf nodes
    rightBoundary(root->right, ans); // Collect right boundary
    return ans;
}

Time Complexity - O(n), where ‘n’ is the total number of nodes in the binary tree.

Since we are traversing for left and right boundaries in a binary tree, and this will take at the most linear time. Also, traversing for leaf nodes can also be performed in linear time. Hence, the overall time complexity is O(n).
Space Complexity- O(n), where ‘n’ is the total number of nodes in the binary tree.

The recursion stack can grow at the maximum height of the binary tree. In the worst-case scenario, the height of a binary tree can be up to n (Skewed Trees). Hence the overall space complexity will be O(n).