Boundary Traversal of Binary Tree in DSA Go - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Add root to boundary

↓

Traverse left boundary down

↓

Add leaf nodes from left to right

↓

Traverse right boundary up

↓

Combine all parts for final boundary

Start from root, add left boundary top-down, then leaves left to right, then right boundary bottom-up to get full boundary.

Execution Sample

DSA Go

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

This code collects the boundary nodes of a binary tree in anti-clockwise order.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	1	root points to Node(1)	Boundary: [1]
2	Add left boundary top-down	2	current moves down left boundary	Boundary: [1, 2, 4]
3	Add leaf nodes left subtree	4, 7	traverse leaves	Boundary: [1, 2, 4, 7]
4	Add leaf nodes right subtree	8, 9	traverse leaves	Boundary: [1, 2, 4, 7, 8, 9]
5	Add right boundary bottom-up	3, 6	current moves up right boundary	Boundary: [1, 2, 4, 7, 8, 9, 6, 3]
6	Traversal complete	nil	none	Final Boundary: [1, 2, 4, 7, 8, 9, 6, 3]

💡 All boundary nodes visited in anti-clockwise order, traversal ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
res (boundary list)	[]	[1, 2, 4]	[1, 2, 4, 7]	[1, 2, 4, 7, 8, 9]	[1, 2, 4, 7, 8, 9, 6, 3]	[1, 2, 4, 7, 8, 9, 6, 3]
current (left boundary)	Node(2)	Node(4)	nil	nil	nil	nil
current (right boundary)	Node(3)	Node(6)	nil	nil	nil	nil

Key Moments - 3 Insights

Why do we add leaf nodes separately after left boundary traversal?

Left boundary traversal adds only non-leaf nodes on the left edge (see Step 2). Leaf nodes are added separately (Steps 3 and 4) to avoid duplicates and to include leaves from both left and right subtrees.

Why is the right boundary added bottom-up?

Right boundary nodes are added bottom-up (Step 5) to maintain anti-clockwise order. Adding them top-down would reverse the boundary order.

What happens if the root has no left or right child?

If root has no left or right child, left and right boundary traversals add nothing, and only root and leaf nodes (which may be root itself) are added (Step 1 and leaf steps).

Visual Quiz - 3 Questions

Look at the execution table, what is the boundary list after Step 3?

A [1, 2, 4, 7]

B [1, 2, 4]

C [1, 2, 4, 7, 8]

D [1, 2]

💡 Hint

Check the 'Visual State' column at Step 3 in the execution_table.

At which step does the right boundary get added to the boundary list?

A Step 2

B Step 5

C Step 4

D Step 3

💡 Hint

Look for 'Add right boundary bottom-up' operation in the execution_table.

If the tree had no right subtree, how would the final boundary list change?

A It would exclude nodes 2 and 4

B It would include extra leaf nodes from right

C It would exclude nodes 3 and 6

D It would be empty

💡 Hint

Refer to variable_tracker and execution_table steps involving right boundary nodes.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root value
- Traverse left boundary top-down (exclude leaves)
- Add all leaf nodes left to right
- Traverse right boundary bottom-up (exclude leaves)
- Combine all for anti-clockwise boundary
- Avoid duplicates by separating leaves

Full Transcript

Boundary traversal of a binary tree collects nodes on the outer edge in anti-clockwise order. We start at the root, add it to the boundary list. Then we traverse the left boundary from top to bottom, adding only non-leaf nodes. Next, we add all leaf nodes from left subtree and right subtree in left to right order. Finally, we traverse the right boundary from bottom to top, adding non-leaf nodes. This order ensures the boundary is collected without duplicates and in correct anti-clockwise order. The execution table shows each step with nodes visited and how the boundary list grows. Key moments clarify why leaves are added separately and why right boundary is added bottom-up. The visual quiz tests understanding of these steps and the final boundary list.

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