Boundary Traversal of a Binary Tree - Iterative - Visualization

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, perform the boundary traversal using an **iterative approach**. The boundary traversal involves printing all the nodes on the boundary in a specific order: (1) root node, (2) left boundary (excluding leaves), (3) all leaf nodes (from left to right), and (4) right boundary (excluding leaves, in reverse order). The goal is to return a list of node values that represent the boundary traversal of the tree.

Examples❯

Input Tree Boundary Traversal Output Description
[1, 2, 3, 4, 5, null, 6]
[1, 2, 4, 5, 6, 3] Standard binary tree with full left boundary, leaves, and right boundary
[1]
[1] Single-node tree (root is the only boundary and leaf)
[] [] Empty tree with no nodes
[1, 2, null, 3, null, null, null, 4]
[1, 2, 3, 4] Left-skewed binary tree, all nodes are on the boundary
[1, null, 2, null, null, null, 3]
[1, 3, 2] Right-skewed binary tree, traversed in left boundary → leaves → reversed right boundary
[1, 2, 3, null, null, 4, 5]
[1, 2, 4, 5, 3] Tree with internal leaves on both sides of the subtree

Solution❯

Understanding the Problem

In this problem, we are given a binary tree, and we need to return its boundary traversal in an anti-clockwise direction. The boundary traversal includes three parts:

  • Left boundary: All the nodes from the root to the left-most node, excluding leaf nodes.
  • Leaf nodes: All the leaf nodes from left to right.
  • Right boundary: All the nodes from the right-most node to the root, excluding leaf nodes, and in reverse order.

To solve this, we must carefully avoid duplicates (especially leaf nodes appearing in both boundaries), and ensure we handle different tree shapes correctly.

Step-by-Step Solution with Example

Step 1: Choose an Example


      1
     /     2   3
   /      4   5   6
     /     7   8

In this binary tree:

  • Left Boundary: 1 → 2 (exclude 4 and 5 as they are leaf or part of leaf path)
  • Leaves: 4, 7, 8, 6 (from left to right)
  • Right Boundary: 3 (reverse order, exclude 6 as it's a leaf)

Expected Boundary Traversal: [1, 2, 4, 7, 8, 6, 3]

Step 2: Add Root

Always include the root first, unless it's the only node (handled as edge case). So, add 1.

Step 3: Traverse Left Boundary

Starting from root.left (i.e., 2), go down keeping only non-leaf nodes: add 2.

Step 4: Collect Leaf Nodes

Do a full traversal and collect all nodes with no left or right child: 4, 7, 8, 6

Step 5: Traverse Right Boundary

Start from root.right (i.e., 3) and collect non-leaf nodes in bottom-up order: [3]

Step 6: Combine All Parts

Merge: [1] + [2] + [4, 7, 8, 6] + [3] = [1, 2, 4, 7, 8, 6, 3]

Edge Cases

Case 1: Empty Tree

If the tree is empty (root == null), return []

Case 2: Tree with Only Root Node

When there's only one node, it is both root and leaf. Output is [root]

Case 3: Left Skewed Tree

All nodes are part of the left boundary or leaves. Example:


    1
   /
  2
 /
3

Boundary traversal: [1, 2, 3]

Case 4: Right Skewed Tree

No left boundary. Only root, leaves, and right boundary exist:


1
   2
       3

Boundary traversal: [1, 3, 2]

Case 5: Tree with Only Left and Right Leaf


    1
   /   2   3

Boundary traversal: [1, 2, 3] (2 and 3 are leaves)

Finally

Boundary traversal of a binary tree is not just about walking around the edges — it's about understanding the structure and breaking it into meaningful parts: left boundary, leaves, and right boundary. Be careful not to include duplicates and ensure you handle edge cases like skewed or empty trees. A good approach always starts with understanding the structure and step-by-step traversal with clear rules.

Algorithm Steps❯

  1. If the tree is empty, return an empty result.
  2. Add the root node's value to the result if it is not a leaf.
  3. Traverse the left boundary (excluding leaves) from the root and add the node values to the result.
  4. Add all leaf nodes from left to right to the result.
  5. Traverse the right boundary (excluding leaves) from the root, store the node values, and then add them in reverse order to the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = value;
    node->left = node->right = NULL;
    return node;
}

void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Preorder Traversal: ");
    preorder(root);
    printf("\n");

    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...