199. Binary Tree Right Side View

--

Check out the problem description here.

Solution

Approach 1

Iterative using level order traversal.

You can use level order traversal, with traversing from

a)left to right -here the last node in each level is what contribute to the right view

b)right to left -here the f irst node in each level is what contribute to right view

In the code below, we follow left to right level- order traversal.

`class Solution:    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:        res=[]        q=[]        if root:            q.append([root,0])        while(q):            size = len(q)            for i in range(size):                front = q.pop(0)                x=front[1]                if front[0].left:                    q.append([front[0].left,x-1])                if front[0].right:                    q.append([front[0].right,x+1])                if(i==size-1):                    res.append(front[0].val)        return res`

Time:O(N)

Space:O(N)

Approach 2:

Recursive Solution

Traverse the tree in root,right, left fashion.Since rightmost node in each level is the right view for that particular level

`class Solution:    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:        res=[]        self.rec(root,0,res)        return res                        def rec(self,root,level,res):        if not root:            return        if len(res)==level:            res.append(root.val)        self.rec(root.right,level+1,res)        self.rec(root.left,level+1,res)`

Time:O(N)

Space:O(h)

h->height of tree (stack space)

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.