Construct Binary Tree in O(1)?

This is horribly underspecified, but taking a wild guess at what they wanted:

def generate():
    if coinflip():
        return Node()
    return Node(left=None, right=generate())

O(1) expected runtime, unbounded returned tree size (and unbounded possible runtime, including running forever with probability 0). We randomly decide whether to keep making the tree deeper with probability 50% each time.

This is both O(1) runtime and unbounded. The contents of the tree is determined during generate().

#include <stdlib.h>
#include <string>

class node {
  std::string _value;
  unsigned int _left_seed;
  unsigned int _right_seed;
  bool _right_exists;
  bool _left_exists;

public:
  inline node(unsigned int seed,std::string const& value)
  {
    _value = value;
    _left_seed = rand_r(&seed);
    _right_seed = rand_r(&seed);
    _left_exists = true; //rand_r(&seed)>5; // depends on what 'unbounded' means
    _right_exists = true; //rand_r(&seed)>5;
  }

  inline node *get_left()
  {
    if (!_left_exists) return NULL;

    unsigned int tseed = _left_seed;
    char ch = '0' + rand_r(&tseed) % 5;

    return new node(tseed,std::string(_value) + ch);
  }

  inline node *get_right()
  {
    if (!_right_exists) return NULL;

    unsigned int tseed = _right_seed;
    char ch = '5' + rand_r(&tseed) % 5;

    return new node(tseed,std::string(_value) + ch);
  }

  inline const std::string& get_value()
  {
    return(_value);
  }
};

static node *generate()
{
  std::string str("");
  return new node(random(),str);
}