Boundary Traversal of a Binary Tree - Iterative Approach

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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❯

Case 1: Empty Tree

If the binary tree is empty (i.e., the root is null), then there are no nodes to include in the boundary traversal. Hence, the result is an empty list: [].

Case 2: Tree with Only Root Node

When the binary tree consists of just a root node and no children, the root itself is considered a boundary (and also a leaf). So the result should simply be the value of the root node: [root].

Case 3: General Binary Tree with Left & Right Subtrees

In a full or semi-full binary tree, the boundary traversal includes multiple components:

  • Root: Always comes first unless it's a leaf (if so, it’s only printed once in the leaf section).
  • Left boundary: All the nodes along the left edge, top to bottom, excluding leaves.
  • Leaves: All the leaf nodes from left to right (left subtree leaves come before right subtree leaves).
  • Right boundary: All the nodes along the right edge, bottom to top, excluding leaves. This is added at the end in reverse order.

This case demonstrates how the traversal combines different sections in a defined order to form the complete boundary view of the tree.

Case 4: Left Skewed Tree

In a left-skewed tree, all nodes are either part of the left boundary or are leaves. The traversal order will include all these nodes from top to bottom. The right boundary is empty in this case.

Case 5: Right Skewed Tree

In a right-skewed tree, only the root and right boundary nodes exist. The left boundary is absent. We add the right boundary nodes in reverse order (bottom to top), except leaves, and then add the leaves (if any). So the output includes root → leaves (if any) → right boundary in reverse.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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))