Binary Tree Right Side View

1. Problem Description

Given a binary tree, imagine standing on its right side. Return the values of the nodes visible from the right, ordered from top to bottom.

2. Approach

1. Use level-order traversal and take the last element of each level

3. Implementation

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    var res []int
    currentLineLast := root
    var nextLineLast *TreeNode
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
            queue = append(queue, node.Left)
            nextLineLast = node.Left
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            nextLineLast = node.Right
        }
        if node == currentLineLast {
            res = append(res, node.Val)
            currentLineLast = nextLineLast
        }
    }

    return res
}

4. References

• 199. Binary Tree Right Side View - LeetCode