Boundary Traversal of Binary Tree in DSA Go

Mental Model

We want to visit all the nodes on the edges of a tree in a specific order: left edge, leaves, then right edge.

Analogy: Imagine walking around the outside of a park fence: you first walk down the left side, then along the bottom (leaves), then up the right side, seeing all the boundary points.

      1
     / \
    2   3
   / \   \
  4   5   6
     / \  /
    7  8 9

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 Goal: Print boundary traversal in order: left boundary, leaves, right boundary

Goal: Print all boundary nodes in anti-clockwise order without duplicates

Step 1: Add root node 1 to boundary

Boundary: 1

Why: Root is always part of boundary

Step 2: Traverse left boundary excluding leaves: add 2

Boundary: 1 -> 2

Why: Left boundary nodes are added top-down excluding leaves

Step 3: Add leaf nodes from left subtree: 4, 7 and 8

Boundary: 1 -> 2 -> 4 -> 7 -> 8

Why: Leaves are added from left to right

Step 4: Add leaf nodes from right subtree: 9 from node 6

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9

Why: Leaves on right subtree added after left subtree leaves

Step 5: Traverse right boundary excluding leaves bottom-up: add 6 then 3

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Why: Right boundary nodes added bottom-up excluding leaves to avoid duplicates

Result:

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

func isLeaf(node *Node) bool {
	return node.Left == nil && node.Right == nil
}

func addLeftBoundary(node *Node, res *[]int) {
	curr := node.Left
	for curr != nil {
		if !isLeaf(curr) {
			*res = append(*res, curr.Val) // add left boundary node
		}
		if curr.Left != nil {
			curr = curr.Left // go left if possible
		} else {
			curr = curr.Right // else go right
		}
	}
}

func addLeaves(node *Node, res *[]int) {
	if node == nil {
		return
	}
	if isLeaf(node) {
		*res = append(*res, node.Val) // add leaf node
		return
	}
	addLeaves(node.Left, res)  // traverse left subtree
	addLeaves(node.Right, res) // traverse right subtree
}

func addRightBoundary(node *Node, res *[]int) {
	curr := node.Right
	stack := []int{}
	for curr != nil {
		if !isLeaf(curr) {
			stack = append(stack, curr.Val) // collect right boundary nodes
		}
		if curr.Right != nil {
			curr = curr.Right // go right if possible
		} else {
			curr = curr.Left // else go left
		}
	}
	// add right boundary nodes in reverse order
	for i := len(stack) - 1; i >= 0; i-- {
		*res = append(*res, stack[i])
	}
}

func boundaryTraversal(root *Node) []int {
	res := []int{}
	if root == nil {
		return res
	}
	res = append(res, root.Val) // add root
	addLeftBoundary(root, &res) // add left boundary
	addLeaves(root, &res)       // add leaves
	addRightBoundary(root, &res) // add right boundary
	return res
}

func main() {
	root := &Node{1, nil, nil}
	root.Left = &Node{2, nil, nil}
	root.Right = &Node{3, nil, nil}
	root.Left.Left = &Node{4, nil, nil}
	root.Left.Right = &Node{5, nil, nil}
	root.Left.Right.Left = &Node{7, nil, nil}
	root.Left.Right.Right = &Node{8, nil, nil}
	root.Right.Right = &Node{6, nil, nil}
	root.Right.Right.Left = &Node{9, nil, nil}

	boundary := boundaryTraversal(root)
	for i, v := range boundary {
		if i == len(boundary)-1 {
			fmt.Printf("%d -> null", v)
		} else {
			fmt.Printf("%d -> ", v)
		}
	}
	fmt.Println()
}

res = append(res, root.Val) // add root

Add root node to result

curr := node.Left for curr != nil { if !isLeaf(curr) { *res = append(*res, curr.Val) // add left boundary node } if curr.Left != nil { curr = curr.Left // go left if possible } else { curr = curr.Right // else go right } }

Traverse left boundary top-down excluding leaves

if isLeaf(node) { *res = append(*res, node.Val) // add leaf node return } addLeaves(node.Left, res) // traverse left subtree addLeaves(node.Right, res) // traverse right subtree

Add all leaf nodes from left to right

curr := node.Right stack := []int{} for curr != nil { if !isLeaf(curr) { stack = append(stack, curr.Val) // collect right boundary nodes } if curr.Right != nil { curr = curr.Right // go right if possible } else { curr = curr.Left // else go left } } for i := len(stack) - 1; i >= 0; i-- { *res = append(*res, stack[i]) }

Traverse right boundary bottom-up excluding leaves using stack

Output

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each node at most once during traversal

Space: O(n) for the output list and recursion stack in worst case

vs Alternative: Naive approach might check each node multiple times or use extra flags, increasing complexity

Edge Cases

Empty tree

Returns empty boundary list

DSA Go

if root == nil {
	return res
}

Tree with only root node

Returns root as boundary since it is also a leaf

DSA Go

res = append(res, root.Val) // add root

Tree with only left subtree

Left boundary and leaves are added correctly, right boundary is empty

DSA Go

addRightBoundary(root, &res) // handles nil right subtree gracefully

When to Use This Pattern

When asked to print all nodes on the edges of a binary tree in order, use boundary traversal to collect left boundary, leaves, and right boundary separately to avoid duplicates.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both boundary and leaf traversal
Fix: Exclude leaf nodes when adding left and right boundaries

Mistake: Adding right boundary nodes top-down causing wrong order
Fix: Collect right boundary nodes first, then add them in reverse order

Summary

Prints all nodes on the boundary of a binary tree in anti-clockwise order.

Use when you need to visit only the outer edge nodes of a tree without duplicates.

Separate left boundary, leaves, and right boundary traversal to avoid duplicates and maintain order.