NUHMAN.com

Problem Statement

Given a binary tree, imagine you are standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Function Signature:

go

func rightSideView(root *TreeNode) []int

Example 1:

go

root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Right = &TreeNode{Val: 5}
root.Right.Right = &TreeNode{Val: 4}
fmt.Println(rightSideView(root)) // Output: [1, 3, 4]

Example 2:

go

root := &TreeNode{Val: 1}
fmt.Println(rightSideView(root)) // Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach

To solve this problem, we can perform a Level Order Traversal (BFS) of the binary tree and record the rightmost node at each level. This will allow us to simulate the view from the right side of the tree.

Steps:

1. Level Order Traversal (BFS):

• Traverse the binary tree level by level.
• For each level, collect the last (rightmost) node at that level.
• Use a queue to help with the BFS traversal.

1. Queue Operations:

• Start by enqueueing the root node.
• For each level, enqueue all nodes at that level, but only add the rightmost node (last node processed at each level) to the result.

1. Edge Case:

• If the tree is empty (root == nil), return an empty slice.

Time Complexity:

• O(n), where n is the number of nodes in the binary tree. We visit each node once in the level order traversal.

Space Complexity:

• O(n), for the queue used during the BFS traversal. In the worst case, the queue will contain all the nodes at a single level, which could be up to n/2 nodes.

Go Implementation

go

package main

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Function to return the right side view of the binary tree
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    result := []int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        
        // Traverse all nodes at the current level
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:] // Dequeue the node
            
            // If it's the last node at this level, add it to the result
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            // Enqueue the left and right children
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }

    return result
}

func main() {
    // Example 1
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Right = &TreeNode{Val: 5}
    root.Right.Right = &TreeNode{Val: 4}
    fmt.Println(rightSideView(root)) // Output: [1, 3, 4]

    // Example 2
    root2 := &TreeNode{Val: 1}
    fmt.Println(rightSideView(root2)) // Output: [1]
}

Explanation of the Code:

1. TreeNode Struct:

• This defines the structure of a binary tree node, which has a value (Val), and pointers to its left and right child nodes.

2. rightSideView Function:

• Input: The function takes a pointer to the root node of the binary tree (root).
• Edge Case: If root is nil, the tree is empty, so we return an empty slice.
• BFS with Queue:
• We initialize a queue with the root node.
• For each level, we process all nodes at that level:
• The last node processed (rightmost node) is added to the result.
• We enqueue the left and right children of each node.
• Result: We return the list of rightmost nodes at each level, which simulates the view from the right side.

3. Main Function:

• In the main function, two test cases are given to validate the solution.

Example Walkthrough

Example 1:

Input: root = [1, 2, 3, null, 5, null, 4]

The tree structure looks like:

markdown

       1
      / \
     2   3
      \    \
       5    4

1. Level 0 (Root):

• The only node is 1, so the rightmost node is 1.

1. Level 1:

• The nodes are 2 and 3. The rightmost node is 3.

1. Level 2:

• The nodes are 5 and 4. The rightmost node is 4.

Output: [1, 3, 4]

Example 2:

Input: root = [1]

The tree structure is:

markdown

    1

1. Level 0 (Root):

• The only node is 1, so the rightmost node is 1.

Output: [1]

Conclusion

The LeetCode 199: Binary Tree Right Side View problem is solved efficiently using BFS. By processing each level and selecting the rightmost node, we simulate the right-side view of the tree. The time complexity is O(n) and the space complexity is O(n), making this approach both time and space efficient for a binary tree of size n.