/* Common leetcode.com problem's scaffold code
 */
#ifndef RADII_LEETCODE
#define RADII_LEETCODE

#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <typeinfo>
#include <vector>

/* Below TreeNode definition is copied from the problem at
 https://leetcode.com/problems/path-sum-iii/ */
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) {}
};
/* Above TreeNode definition is copied from the problem at
https://leetcode.com/problems/path-sum-iii/ */

//
struct node_and_explored {
  TreeNode *node;
  bool explored;
};

std::ostream &operator<<(std::ostream &out, TreeNode *node) {
  out << "{";
  if (!node) {
    out << "}";
    return out;
  }

  std::queue<TreeNode *> bfs;
  bfs.push(node);
  while (bfs.size()) {
    node = bfs.front();
    bfs.pop();
    if (node) {
      out << node->val << ", ";
      bfs.push(node->left);
      bfs.push(node->right);
    } else
      out << "null, ";
  }
  out << "\b\b}";
  return out;
}

template <typename T = int>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &vec) {
  out << "{";
  if (!vec.size()) {
    out << "}";
    return out;
  }
  for (T e : vec) {
    std::cout << e << ", ";
  }
  if (typeid(vec[0]) == typeid(std::string))
    out << '\b';
  out << " \b\b}";
  return out;
}

template <typename T = int>
std::ostream &operator<<(std::ostream &out,
                         const std::vector<std::vector<T>> &vec_2d) {
  out << "{";
  if (!vec_2d.size()) {
    out << "}";
    return out;
  }
  for (const std::vector<T> &vec : vec_2d)
    out << vec << ", ";
  out << " \b\b}";
  return out;
}

template <typename T = int> TreeNode *vector_to_tree(std::vector<T> &&vec) {
  if (!vec.size())
    return nullptr;

  std::vector<TreeNode *> *nodes = new std::vector<TreeNode *>;
  for (std::size_t i = 0, upto = vec.size(); i < upto; i++) {
    // NOTE: cannot use T_MAX in problem input since treating it as empty node
    if (vec[i] == std::numeric_limits<T>::max())
      nodes->emplace_back(nullptr);
    else
      nodes->emplace_back(new TreeNode(vec[i]));
  }

  for (std::size_t i = 0, upto = vec.size(); i < upto; i++) {
    if (!(*nodes)[i])
      continue;
    std::size_t left = 2 * i + 1, right = 2 * i + 2;
    if (left < upto)
      (*nodes)[i]->left = (*nodes)[left];
    if (right < upto)
      (*nodes)[i]->right = (*nodes)[right];
  }

  return (*nodes)[0];
}

#endif