Boundary Traversal of Binary Tree in DSA C++ - Time & Space Complexity

Time Complexity: Boundary Traversal of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time taken grows when we do a boundary traversal of a binary tree.

Specifically, how the number of nodes affects the work done to collect the boundary nodes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printBoundary(Node* root) {
    if (!root) return;
    cout << root->data << " ";
    printLeftBoundary(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRightBoundary(root->right);
}

// Helper functions traverse parts of the tree
void printLeftBoundary(Node* node) {
    while (node) {
        if (!isLeaf(node)) cout << node->data << " ";
        if (node->left) node = node->left;
        else node = node->right;
    }
}

This code prints the boundary nodes of a binary tree in anti-clockwise order: root, left boundary, leaves, and right boundary.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing nodes in the tree to print left boundary, leaves, and right boundary.
• How many times: Each node is visited at most once during these traversals.

How Execution Grows With Input

As the number of nodes increases, the traversal visits each node once to check if it belongs to the boundary.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The boundary traversal only visits boundary nodes, so it must be faster than visiting all nodes."

[OK] Correct: To find boundary nodes, the algorithm must check many nodes, including leaves and internal nodes, so it ends up visiting all nodes once.

Interview Connect

Understanding this traversal helps you reason about tree traversals and how to efficiently visit nodes in a specific order, a useful skill in many coding problems.

Self-Check

"What if we changed the tree to be skewed (all nodes only have one child)? How would the time complexity change?"