Construct Binary Tree in O(1)?

Question

My friend was asked this question in an interview:

Generate a finite but arbitrarily large binary tree in O(1). The method generate() should return a binary tree whose size is unbounded but finite.

We both cogitated over it for a long time after the interview, but we are only able to come up with O(n) solutions at best.

How would we generate in O(1)? Is it even possible? Is there something more to it?

Answer 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.

Answer 2

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);
}