Boundary Traversal of a Binary Tree

Problem and examples

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.

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

Explore Boundary Traversal of a Binary Tree - Iterative

Load an example or enter your own input. Use the player controls to follow each change.

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.

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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

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

    cout << "Preorder Traversal: ";
    preorder(root);
    cout << endl;

    return 0;
}

Python implementation

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

def preorder(root):
    if root is None:
        return
    print(root.val, end=' ')
    preorder(root.left)
    preorder(root.right)

if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    print("Preorder Traversal:", end=' ')
    preorder(root)
    print()

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int value) {
        val = value;
        left = right = null;
    }
}

public class PreorderTraversal {
    public static void preorder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("Preorder Traversal: ");
        preorder(root);
        System.out.println();
    }
}

JavaScript implementation

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function preorder(root) {
    if (!root) return;
    process.stdout.write(root.val + ' ');
    preorder(root.left);
    preorder(root.right);
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

process.stdout.write("Preorder Traversal: ");
preorder(root);
console.log();

Go implementation

package main

import "fmt"

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func preorder(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Printf("%d ", root.val)
    preorder(root.left)
    preorder(root.right)
}

func main() {
    root := &TreeNode{val: 1}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 3}
    root.left.left = &TreeNode{val: 4}
    root.left.right = &TreeNode{val: 5}

    fmt.Print("Preorder Traversal: ")
    preorder(root)
    fmt.Println()
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn preorder(root: &Option<Box<TreeNode>>) {
    if let Some(node) = root {
        print!("{} ", node.val);
        preorder(&node.left);
        preorder(&node.right);
    }
}

fn main() {
    let mut root = Box::new(TreeNode::new(1));
    root.left = Some(Box::new(TreeNode::new(2)));
    root.right = Some(Box::new(TreeNode::new(3)));
    root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));
    root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));

    print!("Preorder Traversal: ");
    preorder(&Some(root));
    println!();
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun preorder(root: TreeNode?) {
    if (root == null) return
    print("${root.value} ")
    preorder(root.left)
    preorder(root.right)
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    root.left!!.right = TreeNode(5)

    print("Preorder Traversal: ")
    preorder(root)
    println()
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func preorder(_ root: TreeNode?) {
    guard let node = root else { return }
    print(node.val, terminator: " ")
    preorder(node.left)
    preorder(node.right)
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)

print("Preorder Traversal:", terminator: " ")
preorder(root)
print()

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function preorder(root: TreeNode | null): void {
    if (!root) return;
    process.stdout.write(root.val + ' ');
    preorder(root.left);
    preorder(root.right);
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

process.stdout.write("Preorder Traversal: ");
preorder(root);
console.log();