Boundary Traversal of Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal on a Simple Binary Tree

What is the output of the boundary traversal for the given binary tree?

DSA Go

package main

import "fmt"

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

func boundaryTraversal(root *Node) []int {
    if root == nil {
        return []int{}
    }
    var res []int
    res = append(res, root.data)

    // Left boundary (excluding leaf)
    curr := root.left
    for curr != nil {
        if curr.left != nil || curr.right != nil {
            res = append(res, curr.data)
        }
        if curr.left != nil {
            curr = curr.left
        } else {
            curr = curr.right
        }
    }

    // Leaves
    var addLeaves func(*Node)
    addLeaves = func(node *Node) {
        if node == nil {
            return
        }
        if node.left == nil && node.right == nil {
            res = append(res, node.data)
            return
        }
        addLeaves(node.left)
        addLeaves(node.right)
    }
    addLeaves(root.left)
    addLeaves(root.right)

    // Right boundary (excluding leaf) in reverse
    var stack []int
    curr = root.right
    for curr != nil {
        if curr.left != nil || curr.right != nil {
            stack = append(stack, curr.data)
        }
        if curr.right != nil {
            curr = curr.right
        } else {
            curr = curr.left
        }
    }
    for i := len(stack) - 1; i >= 0; i-- {
        res = append(res, stack[i])
    }

    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.right.left = &Node{6, nil, nil}
    root.right.right = &Node{7, nil, nil}

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

A [1, 2, 4, 5, 6, 7, 3]

B [1, 2, 4, 5, 7, 6, 3]

C [1, 2, 4, 5, 6, 3, 7]

D [1, 4, 5, 6, 7, 2, 3]

💡 Hint

Remember to include left boundary (excluding leaves), then leaves, then right boundary in reverse order.

The boundary traversal starts with root, then left boundary excluding leaves (2), then leaves (4,5,6,7), then right boundary excluding leaves in reverse (3). So the output is [1, 2, 4, 5, 6, 7, 3].

🧠 Conceptual

intermediate

Understanding Boundary Traversal Components

Which of the following correctly describes the order of nodes visited in a boundary traversal of a binary tree?

A Root node, all leaf nodes from left to right, left boundary excluding leaves, right boundary excluding leaves in reverse

B All leaf nodes from left to right, root node, left boundary excluding leaves, right boundary excluding leaves in reverse

C Root node, left boundary excluding leaves, all leaf nodes from left to right, right boundary excluding leaves in reverse

D Left boundary excluding leaves, root node, right boundary excluding leaves in reverse, all leaf nodes from left to right

💡 Hint

Think about the natural boundary around the tree starting from the root.

Boundary traversal visits the root first, then the left boundary excluding leaves, then all leaves from left to right, and finally the right boundary excluding leaves in reverse order.

🔧 Debug

advanced

Identify the Bug in Boundary Traversal Code

Given the following snippet from a boundary traversal function, what error will it cause if root == nil? func boundaryTraversal(root *Node) []int { var res []int res = append(res, root.data) curr := root.left for curr != nil { if curr.left != nil || curr.right != nil { res = append(res, curr.data) } if curr.left != nil { curr = curr.left } else { curr = curr.right } } // Leaves and right boundary code omitted for brevity return res }

A Compilation error due to missing return statement

B Panic due to nil pointer dereference when accessing root.data if root is nil

C No error, returns slice with only root data

D Infinite loop because curr never becomes nil

💡 Hint

Check if root is nil before accessing its fields.

If root is nil, accessing root.data causes a runtime panic due to nil pointer dereference.

❓ Predict Output

advanced

Boundary Traversal Output for Skewed Tree

What is the output of the boundary traversal for the following left-skewed binary tree? Tree structure: 1 | 2 | 3 | 4 Code snippet: func main() { root := &Node{1, nil, nil} root.left = &Node{2, nil, nil} root.left.left = &Node{3, nil, nil} root.left.left.left = &Node{4, nil, nil} result := boundaryTraversal(root) fmt.Println(result) }

A [1, 2, 4, 3]

B [1, 4, 3, 2]

C [4, 3, 2, 1]

D [1, 2, 3, 4]

💡 Hint

In a skewed tree, left boundary and leaves overlap.

The boundary traversal visits root (1), left boundary excluding leaves (2,3), leaves (4), and no right boundary. So output is [1, 2, 3, 4].

🚀 Application

expert

Number of Nodes in Boundary Traversal Result

Given a perfect binary tree of height 2 (levels 0 to 2), how many nodes will be in the boundary traversal output?

A 7

B 8

C 9

D 10

💡 Hint

Count root (1), left boundary excluding leaves (1), leaves (4), and right boundary excluding leaves (1).

A perfect binary tree of height 2 (levels 0 to 2) has 7 nodes, all of which are on the boundary: root (1), left boundary excluding leaves (1 node at level 1 left), leaves (4 at level 2), right boundary excluding leaves (1 node at level 1 right). Total: 7.