199. Tree right side view

199_solution1_iterative.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 100 // constraint: number of nodes is in [0, 100]

// returns the rightmost value of each level; sets *returnSize to the level count
int *rightSideView(struct TreeNode *root, int *returnSize) {
  int *res = malloc(MAX_NODES * sizeof(int));
  *returnSize = 0;
  if (!root)
    return res;

  struct TreeNode *queue[MAX_NODES];
  int head = 0, tail = 0;
  queue[tail++] = root;

  while (head < tail) {
    int sz = tail - head;
    for (int i = 0; i < sz; i++) {
      struct TreeNode *node = queue[head++];

      if (i == sz - 1)
        res[(*returnSize)++] = node->val;

      if (node->left)
        queue[tail++] = node->left;
      if (node->right)
        queue[tail++] = node->right;
    }
  }
  return res;
}

199_solution2_recursive.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 100 // constraint: number of nodes is in [0, 100]

// visit right first, so the first node seen at each depth is the rightmost
static void dfs(struct TreeNode *node, int depth, int *res, int *size) {
  if (!node)
    return;

  if (depth == *size)
    res[(*size)++] = node->val;

  dfs(node->right, depth + 1, res, size);
  dfs(node->left, depth + 1, res, size);
}

// returns the rightmost value of each level; sets *returnSize to the level count
int *rightSideView(struct TreeNode *root, int *returnSize) {
  int *res = malloc(MAX_NODES * sizeof(int));
  *returnSize = 0;
  dfs(root, 0, res, returnSize);
  return res;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

199_solution1_iterative.cpp

#include "tree_node.h"
#include <queue>
#include <vector>

using namespace std;

vector<int> rightSideView(TreeNode *root) {
  vector<int> res;
  if (!root)
    return res;

  queue<TreeNode *> q;
  q.push(root);

  while (!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
      TreeNode *node = q.front();
      q.pop();

      if (i == sz - 1)
        res.push_back(node->val);

      if (node->left)
        q.push(node->left);
      if (node->right)
        q.push(node->right);
    }
  }
  return res;
}

199_solution2_recursive.cpp

#include "tree_node.h"
#include <vector>

using namespace std;

class Solution {
public:
  vector<int> rightSideView(TreeNode *root) {
    vector<int> res;
    dfs(root, 0, res);
    return res;
  }

private:
  void dfs(TreeNode *node, int depth, vector<int> &res) {
    if (!node)
      return;

    if (depth == res.size())
      res.push_back(node->val);

    dfs(node->right, depth + 1, res);
    dfs(node->left, depth + 1, res);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

199_solution1_iterative.go

package trees

func rightSideView(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        sz := len(queue)
        for i, node := range queue[:sz] {
            if i == sz-1 {
                res = append(res, node.Val)
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        queue = queue[sz:]
    }
    return res
}

199_solution2_recursive.go

package trees

func rightSideView(root *TreeNode) []int {
    res := []int{}

    // visit right first, so the first node seen at each depth is the rightmost
    var dfs func(node *TreeNode, depth int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }

        if depth == len(res) {
            res = append(res, node.Val)
        }

        dfs(node.Right, depth+1)
        dfs(node.Left, depth+1)
    }

    dfs(root, 0)
    return res
}

tree_node.go

package trees

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

199_solution1_iterative.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;

        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode node = q.poll();

                if (i == sz - 1)
                    res.add(node.val);

                if (node.left != null)
                    q.add(node.left);
                if (node.right != null)
                    q.add(node.right);
            }
        }
        return res;
    }
}

199_solution2_recursive.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    // visit right first, so the first node seen at each depth is the rightmost
    private void dfs(TreeNode node, int depth, List<Integer> res) {
        if (node == null)
            return;

        if (depth == res.size())
            res.add(node.val);

        dfs(node.right, depth + 1, res);
        dfs(node.left, depth + 1, res);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

199_solution1_iterative.js

const TreeNode = require("./tree_node");

var rightSideView = function (root) {
  const res = [];
  if (!root) return res;

  // index-based queue: avoids the O(n) cost of Array.shift()
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const sz = queue.length - head;
    for (let i = 0; i < sz; i++) {
      const node = queue[head++];

      if (i === sz - 1) res.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return res;
};

199_solution2_recursive.js

const TreeNode = require("./tree_node");

var rightSideView = function (root) {
  const res = [];

  // visit right first, so the first node seen at each depth is the rightmost
  const dfs = (node, depth) => {
    if (!node) return;

    if (depth === res.length) res.push(node.val);

    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  };

  dfs(root, 0);
  return res;
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

199_solution1_iterative.py

from collections import deque
from typing import List, Optional

from tree_node import TreeNode


class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res

        q = deque([root])

        while q:
            sz = len(q)
            for i in range(sz):
                node = q.popleft()

                if i == sz - 1:
                    res.append(node.val)

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return res

199_solution2_recursive.py

from typing import List, Optional

from tree_node import TreeNode


class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        # visit right first, so the first node seen at each depth is the rightmost
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return

            if depth == len(res):
                res.append(node.val)

            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return res

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

199_solution1_iterative.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = Vec::new();

        let mut q = VecDeque::new();
        if let Some(r) = root {
            q.push_back(r);
        }

        while !q.is_empty() {
            let sz = q.len();
            for i in 0..sz {
                let node = q.pop_front().unwrap();
                let node = node.borrow();

                if i == sz - 1 {
                    res.push(node.val);
                }

                if let Some(l) = &node.left {
                    q.push_back(Rc::clone(l));
                }
                if let Some(r) = &node.right {
                    q.push_back(Rc::clone(r));
                }
            }
        }
        res
    }
}

199_solution2_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn right_side_view(root: Link) -> Vec<i32> {
        let mut res = Vec::new();
        Self::dfs(&root, 0, &mut res);
        res
    }

    // visit right first, so the first node seen at each depth is the rightmost
    fn dfs(node: &Link, depth: usize, res: &mut Vec<i32>) {
        if let Some(n) = node {
            let n = n.borrow();

            if depth == res.len() {
                res.push(n.val);
            }

            Self::dfs(&n.right, depth + 1, res);
            Self::dfs(&n.left, depth + 1, res);
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}