Skip to content

199. Binary Tree Right Side ViewΒΆ

Problem Link

The right side view of a binary tree consists of the nodes that are last visible at each level when the tree is viewed from the right. This naturally leads to a level-order traversal, where we add the last node in each level.

Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the tree

Space: \(O(n)\), for the queue used during traversal

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        q = deque([root])
        side = []
        while len(q) > 0:
            size = len(q)
            for i in range(size):
                node = q.pop()
                if i == size-1:
                    side.append(node.val)
                if node.left:
                    q.appendleft(node.left)
                if node.right:
                    q.appendleft(node.right)
        return side

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := make(chan *TreeNode, 100)
    queue <- root
    var side []int
    var size, i int
    var node *TreeNode
    for len(queue) > 0 {
        size = len(queue)
        for i = 0; i < size; i++ {
            node = <-queue
            if i == size-1 {
                side = append(side, node.Val)
            }
            if node.Left != nil {
                queue <- node.Left
            }
            if node.Right != nil {
                queue <- node.Right
            }
        }
    }
    return side
}