Boundary Traversal of Binary Tree in DSA Go - Build from Scratch

Boundary Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to list all family members who are on the outer edge of the tree, starting from the top ancestor, going down the left side, then the leaves from left to right, and finally up the right side.

🎯 Goal: Build a program in Go that performs a boundary traversal of a binary tree. The program will print the nodes on the boundary in the correct order.

📋 What You'll Learn

Define a binary tree node struct called Node with data, left, and right fields

Create a sample binary tree with exactly these nodes and structure:
Root: 20
Left child of 20: 8
Right child of 20: 22
Left child of 8: 4
Right child of 8: 12
Left child of 12: 10
Right child of 12: 14
Right child of 22: 25

Create a helper variable boundaryNodes as a slice of integers to store the boundary traversal result

Implement functions to add left boundary, leaves, and right boundary nodes to boundaryNodes

Print the boundaryNodes slice as the final output

💡 Why This Matters

🌍 Real World

Boundary traversal helps in graphical rendering, image processing, and understanding the outline of hierarchical data structures.

💼 Career

Understanding tree traversals is essential for software engineers working with data structures, algorithms, and system design.

1

Create the binary tree structure

Define a struct called Node with fields data int, left *Node, and right *Node. Then create the binary tree with root node 20 and the exact structure: left child 8, right child 22, left child of 8 is 4, right child of 8 is 12, left child of 12 is 10, right child of 12 is 14, and right child of 22 is 25.

DSA Go

// Define Node struct and create the binary tree with given nodes
// Your code here

Hint

Start by defining the Node struct. Then create the root node and assign its children exactly as described.

2

Create a slice to hold boundary nodes

Create a variable called boundaryNodes as a slice of integers to store the nodes on the boundary.

DSA Go

package main

import "fmt"

type Node struct {
	data  int
	left  *Node
	right *Node
}

func main() {
	root := &Node{data: 20}
	root.left = &Node{data: 8}
	root.right = &Node{data: 22}
	root.left.left = &Node{data: 4}
	root.left.right = &Node{data: 12}
	root.left.right.left = &Node{data: 10}
	root.left.right.right = &Node{data: 14}
	root.right.right = &Node{data: 25}

	// Create boundaryNodes slice here
	// Your code here
}

Hint

Use boundaryNodes := []int{} to create an empty slice of integers.

3

Implement boundary traversal logic

Write functions addLeftBoundary, addLeaves, and addRightBoundary that take root *Node and boundaryNodes *[]int as parameters. Use these functions to add the left boundary (excluding leaves), all leaf nodes, and the right boundary (excluding leaves) to boundaryNodes. In main, first append root.data to boundaryNodes, then call these functions in order.

DSA Go

package main

import "fmt"

type Node struct {
	data  int
	left  *Node
	right *Node
}

func addLeftBoundary(root *Node, boundaryNodes *[]int) {
	// Your code here
}

func addLeaves(root *Node, boundaryNodes *[]int) {
	// Your code here
}

func addRightBoundary(root *Node, boundaryNodes *[]int) {
	// Your code here
}

func main() {
	root := &Node{data: 20}
	root.left = &Node{data: 8}
	root.right = &Node{data: 22}
	root.left.left = &Node{data: 4}
	root.left.right = &Node{data: 12}
	root.left.right.left = &Node{data: 10}
	root.left.right.right = &Node{data: 14}
	root.right.right = &Node{data: 25}

	boundaryNodes := []int{}

	// Append root data
	// Call addLeftBoundary, addLeaves, addRightBoundary
	// Your code here
}

Hint

Use loops and recursion to add nodes to boundaryNodes. Remember to exclude leaf nodes from left and right boundaries.

4

Print the boundary traversal result

Print the boundaryNodes slice in main to display the boundary traversal of the binary tree.

DSA Go

package main

import "fmt"

type Node struct {
	data  int
	left  *Node
	right *Node
}

func addLeftBoundary(root *Node, boundaryNodes *[]int) {
	curr := root.left
	for curr != nil {
		if curr.left != nil || curr.right != nil {
			*boundaryNodes = append(*boundaryNodes, curr.data)
		}
		if curr.left != nil {
			curr = curr.left
		} else {
			curr = curr.right
		}
	}
}

func addLeaves(root *Node, boundaryNodes *[]int) {
	if root == nil {
		return
	}
	if root.left == nil && root.right == nil {
		*boundaryNodes = append(*boundaryNodes, root.data)
		return
	}
	addLeaves(root.left, boundaryNodes)
	addLeaves(root.right, boundaryNodes)
}

func addRightBoundary(root *Node, boundaryNodes *[]int) {
	curr := root.right
	temp := []int{}
	for curr != nil {
		if curr.left != nil || curr.right != nil {
			temp = append(temp, curr.data)
		}
		if curr.right != nil {
			curr = curr.right
		} else {
			curr = curr.left
		}
	}
	for i := len(temp) - 1; i >= 0; i-- {
		*boundaryNodes = append(*boundaryNodes, temp[i])
	}
}

func main() {
	root := &Node{data: 20}
	root.left = &Node{data: 8}
	root.right = &Node{data: 22}
	root.left.left = &Node{data: 4}
	root.left.right = &Node{data: 12}
	root.left.right.left = &Node{data: 10}
	root.left.right.right = &Node{data: 14}
	root.right.right = &Node{data: 25}

	boundaryNodes := []int{}

	boundaryNodes = append(boundaryNodes, root.data)
	addLeftBoundary(root, &boundaryNodes)
	addLeaves(root, &boundaryNodes)
	addRightBoundary(root, &boundaryNodes)

	// Print the boundaryNodes slice
	// Your code here
}

Hint

Use fmt.Println(boundaryNodes) to print the slice showing the boundary traversal.

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