Boundary Traversal of a Binary Tree - Iterative Approach

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

Visualization Player

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:

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❯

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

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isLeaf(node):
    return node.left is None and node.right is None

def addLeftBoundary(root, res):
    cur = root.left
    while cur:
        if not isLeaf(cur):
            res.append(cur.val)
        cur = cur.left if cur.left else cur.right

def addLeaves(root, res):
    if root is None:
        return
    if isLeaf(root):
        res.append(root.val)
    else:
        addLeaves(root.left, res)
        addLeaves(root.right, res)

def addRightBoundary(root, res):
    cur = root.right
    tmp = []
    while cur:
        if not isLeaf(cur):
            tmp.append(cur.val)
        cur = cur.right if cur.right else cur.left
    res.extend(tmp[::-1])

def boundaryTraversal(root):
    if not root:
        return []
    res = []
    if not isLeaf(root):
        res.append(root.val)
    addLeftBoundary(root, res)
    addLeaves(root, res)
    addRightBoundary(root, res)
    return res

if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \   \
    #     4   5   6
    #            /
    #           7
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6, TreeNode(7))))
    print(boundaryTraversal(root))

⬅ Previous TopicDiagonal Traversal of a Binary Tree

Next Topic ⮕Construct a Binary Tree from a String with Bracket Representation

Comments

Loading comments...