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.

Practice

1. What is the main purpose of Boundary Traversal in a binary tree?

easy

A. To print nodes level by level

B. To print all leaf nodes only

C. To print nodes in in-order traversal

D. To print all nodes on the boundary of the tree in an anti-clockwise direction

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree, including left boundary, leaves, and right boundary.

2. Step 2: Compare with other traversals

   Unlike leaf-only or level order, boundary traversal covers all edges in anti-clockwise order.

3. Final Answer:

   To print all nodes on the boundary of the tree in an anti-clockwise direction -> Option D

4. Quick Check:

   Boundary traversal = print edges anti-clockwise [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with leaf node traversal
• Thinking it prints nodes level-wise
• Mixing it with in-order traversal

2. Which of the following Go function signatures correctly represents a function to perform boundary traversal of a binary tree node?

easy

A. func boundaryTraversal(root Node) int

B. func boundaryTraversal(root *Node) []int

C. func boundaryTraversal(root *Node) int

D. func boundaryTraversal(root Node) []Node

Solution

1. Step 1: Understand function input and output

   The function should take a pointer to the root node and return a slice of integers representing node values.

2. Step 2: Check each option

   func boundaryTraversal(root *Node) []int matches input as pointer and output as slice of int, suitable for traversal results.

3. Final Answer:

   func boundaryTraversal(root *Node) []int -> Option B

4. Quick Check:

   Pointer input + slice output = correct signature [OK]

Hint: Use pointer receiver and slice return for traversal [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Returning single int instead of slice
• Returning slice of nodes instead of values

3. Given the following binary tree and Go code snippet, what is the output of the boundary traversal? Tree structure: ``` 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 ``` Go code snippet:

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.Right.Right = &Node{6, nil, nil}
    root.Left.Right.Left = &Node{7, nil, nil}
    root.Left.Right.Right = &Node{8, nil, nil}
    root.Right.Right.Left = &Node{9, nil, nil}

    result := boundaryTraversal(root)
    fmt.Println(result)
}

medium

A. [1 2 4 7 8 9 6 3]

B. [1 2 4 7 8 5 9 6 3]

C. [1 2 4 7 8 9 6]

D. [1 2 4 5 7 8 9 6 3]

Solution

1. Step 1: Identify boundary nodes in anti-clockwise order

   Left boundary: 1, 2, 4 (excluding leaves repeated), Leaves: 4,7,8,9,6, Right boundary: 3 (excluding leaf 6 as it's already included)

2. Step 2: Combine nodes without duplicates

   Boundary traversal = 1 (root), 2 (left boundary), 4 (leaf), 7 (leaf), 8 (leaf), 9 (leaf), 6 (leaf), 3 (right boundary)

3. Final Answer:

   [1 2 4 7 8 9 6 3] -> Option A

4. Quick Check:

   Boundary nodes combined = [1 2 4 7 8 9 6 3] [OK]

Hint: List left boundary, leaves, then right boundary reversed [OK]

Common Mistakes:

• Including internal nodes like 5 in boundary
• Repeating leaf nodes in boundary and leaves
• Wrong order of right boundary nodes

4. The following Go function for boundary traversal has a bug. What is the main issue?

func boundaryTraversal(root *Node) []int {
    if root == nil {
        return []int{}
    }
    result := []int{root.Val}
    addLeftBoundary(root.Left, &result)
    addLeaves(root, &result)
    addRightBoundary(root.Right, &result)
    return result
}

func addLeftBoundary(node *Node, res *[]int) {
    for node != nil {
        if node.Left != nil || node.Right != nil {
            *res = append(*res, node.Val)
        }
        if node.Left != nil {
            node = node.Left
        } else {
            node = node.Right
        }
    }
}

func addLeaves(node *Node, res *[]int) {
    if node == nil {
        return
    }
    if node.Left == nil && node.Right == nil {
        *res = append(*res, node.Val)
        return
    }
    addLeaves(node.Left, res)
    addLeaves(node.Right, res)
}

func addRightBoundary(node *Node, res *[]int) {
    temp := []int{}
    for node != nil {
        if node.Left != nil || node.Right != nil {
            temp = append(temp, node.Val)
        }
        if node.Right != nil {
            node = node.Right
        } else {
            node = node.Left
        }
    }
    for i := len(temp) - 1; i >= 0; i-- {
        *res = append(*res, temp[i])
    }
}

medium

A. Leaves are added twice because addLeaves includes left and right boundary leaves

B. Right boundary nodes are appended in wrong order

C. Left boundary includes leaf nodes which should be excluded

D. Root node is not added to the result

Solution

1. Step 1: Analyze addLeftBoundary function

   It adds nodes if they have left or right child, but does not exclude leaf nodes properly, so leaf nodes may be added twice.

2. Step 2: Check leaf node addition

   Leaves are added separately by addLeaves, so left boundary should exclude leaves to avoid duplicates.

3. Final Answer:

   Left boundary includes leaf nodes which should be excluded -> Option C

4. Quick Check:

   Left boundary must exclude leaves [OK]

Hint: Exclude leaves from left boundary to avoid duplicates [OK]

Common Mistakes:

• Not excluding leaves in left boundary
• Appending right boundary in forward order
• Forgetting to add root node

5. You want to modify the boundary traversal to print nodes in clockwise order starting from root. Which change is correct to achieve this?

hard

A. Traverse right boundary top-down, then leaves right-to-left, then left boundary bottom-up

B. Traverse left boundary top-down, then leaves left-to-right, then right boundary bottom-up

C. Traverse leaves first, then left boundary, then right boundary

D. Traverse right boundary bottom-up, then leaves left-to-right, then left boundary top-down

Solution

1. Step 1: Understand clockwise boundary traversal order

   Clockwise order starts from root, then right boundary top-down, leaves right-to-left, and left boundary bottom-up.

2. Step 2: Match options with traversal order

   Traverse right boundary top-down, then leaves right-to-left, then left boundary bottom-up matches this order exactly, others do not.

3. Final Answer:

   Traverse right boundary top-down, then leaves right-to-left, then left boundary bottom-up -> Option A

4. Quick Check:

   Clockwise = root, right boundary, leaves, left boundary [OK]

Hint: Clockwise = root + right boundary + leaves + left boundary [OK]

Common Mistakes:

• Using left boundary first for clockwise
• Not reversing leaf order for clockwise
• Mixing top-down and bottom-up incorrectly