Partimos de la siguiente función

void mi_funcion(const BinTree &t) {
  if (t.empty()) {
     // No hacemos nada
  } else {
    mi_funcion(t.left());
    mi_funcion(t.right());
    g(t.left());
    g(t.right());
  }
}

Si suponemos que el árbol de entrada t está equilibrado y que tiene tamaño , y que la función g() tiene coste en tiempo lineal con respecto al tamaño del árbol que recibe como parámetro. ¿Cuál es el orden de complejidad de esta función?

Partimos de la siguiente función

void mi_funcion(const BinTree &t) {
  if (t.empty()) {
     // No hacemos nada
  } else {
    mi_funcion(t.left());
    g();
  }
}

Si suponemos que el árbol de entrada t está equilibrado y que tiene tamaño , y que la función g() tiene coste en tiempo constante. ¿Cuál es el orden de complejidad de esta función?

Partimos de la siguiente función

void mi_funcion(const BinTree &t) {
  if (t.empty()) {
     // No hacemos nada
  } else {
    if (h()) {
      mi_funcion(t.left());
    } else {
      mi_funcion(t.right());
    }
    g();
  }
}

Si suponemos que el árbol de entrada t está equilibrado y que tiene tamaño , y que las funciones g() y h() tienen coste en tiempo constante. ¿Cuál es el orden de complejidad de esta función?

Si denota el número de nodos del árbol de entrada, ¿cuál es el coste en tiempo de la función sum_nodes?

int sum_nodes(const BinTree &tree) {
  if (tree.empty()) {
    return 0;
  } else {
    return tree.root() + sum_nodes(tree.left()) + sum_nodes(tree.right());
  }
}