Boundary Traversal of Binary Tree in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Boundary Traversal of a binary tree?

Boundary Traversal is a way to visit all the nodes on the boundary of a binary tree. It includes the left boundary (top to bottom), all leaf nodes (left to right), and the right boundary (bottom to top).

beginner

Which nodes are included in the left boundary during boundary traversal?

The left boundary includes all nodes on the path from the root to the left-most leaf, excluding leaf nodes if they are already counted in the leaf nodes section.

beginner

How do you identify leaf nodes in a binary tree?

Leaf nodes are nodes that do not have any children (no left or right child). They are the bottom-most nodes in the tree.

intermediate

What is the order of nodes visited in boundary traversal?

The order is: root node, left boundary (top to bottom), leaf nodes (left to right), and right boundary (bottom to top).

intermediate

Why do we traverse the right boundary from bottom to top in boundary traversal?

We traverse the right boundary from bottom to top to maintain the anti-clockwise order of the boundary traversal, ensuring nodes are visited in the correct sequence.

Which nodes are NOT included in the left boundary during boundary traversal?

A Leaf nodes already counted in leaf nodes section

B Root node

C All nodes on the left path

D Right child nodes

Leaf nodes are counted separately in the leaf nodes section, so they are excluded from the left boundary to avoid duplication.

In boundary traversal, how are leaf nodes visited?

A From right to left

B From left to right

C Top to bottom

D Bottom to top

Leaf nodes are visited from left to right to cover all leaves in the tree in order.

What is the first node visited in boundary traversal?

A Root node

B Left-most leaf

C Right boundary node

D Right-most leaf

The traversal always starts with the root node.

How is the right boundary traversed in boundary traversal?

A Top to bottom

B Left to right

C Bottom to top

D Right to left

The right boundary is traversed from bottom to top to maintain the anti-clockwise order.

Which of these nodes is NOT part of the boundary traversal?

A Root node

B Leaf nodes

C Left boundary nodes

D Internal nodes not on boundary

Only nodes on the boundary (left boundary, leaves, right boundary, and root) are included, internal nodes inside the tree are not.

Explain the steps to perform boundary traversal of a binary tree.

Think about visiting edges and leaves in an anti-clockwise direction.

Describe how to avoid counting leaf nodes twice in boundary traversal.

Leaves appear in both boundary and leaf sections, so handle carefully.

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