Problem

Generate a finite, but an arbitrarily large binary tree quickly in O(1).

That is, generate() should return a tree whose size is unbounded but finite.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: 
Output: A binary tree
Explanation: 
The generated binary tree can have an arbitrary structure. For example:
	 1
	/ \
   2   3
  /|   |\
 4 5   6 7
 
This is just one of many possible trees that can be generated.

Example 2

1
2
3
4
5
6
7
8
9

Input: 
Output: A binary tree
Explanation:
Another possible output might be a left-leaning tree:
     1
    /
   2
  / 
 3

Solution

Method 1 - Randomized algorithm

Let p be the probability that a node becomes a leaf (in this code, p = 1/2), and x be the probability that the entire tree is finite. The tree will be finite either if we terminate at the current node (probability p) or if we continue (probability 1-p) but both subtrees end up finite (probability x^2). Therefore, the equation is x = p + (1-p)x^2. Solving this yields x = min(p/(1-p), 1). Thus, for p = 1/2, the probability that the tree is finite is indeed 1. However, if p is lower, there is a positive probability that the tree will be infinite.

Approach

  1. Define Node Class with Lazy Evaluation:
    • Create a Node class where left and right children are evaluated lazily.
    • Use random probability to decide whether to create child nodes upon access.
  2. Generate Function:
    • Implement the generate function to instantiate and return the root node of the tree.
  3. Random Expansion:
    • When accessing left or right child, generate the child with a fixed probability (p).
    • This results in an unbounded but finite tree if p is chosen appropriately.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class TreeNode {
    int val;
    private TreeNode left;
    private TreeNode right;
    private boolean isLeftEvaluated;
    private boolean isRightEvaluated;
    
    private static final Random random = new Random();

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.isLeftEvaluated = false;
        this.isRightEvaluated = false;
    }

    public TreeNode() {
        this(1);
    }

    public TreeNode getLeft() {
        if (!isLeftEvaluated) {
            if (random.nextFloat() < 0.5) {
                this.left = new TreeNode();
            }
            isLeftEvaluated = true;
        }
        return this.left;
    }

    public TreeNode getRight() {
        if (!isRightEvaluated) {
            if (random.nextFloat() < 0.5) {
                this.right = new TreeNode();
            }
            isRightEvaluated = true;
        }
        return this.right;
    }
}

public class Solution {
    public TreeNode generate() {
        return new TreeNode();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = solution.generate();
        // This main method is only for testing purposes
        printTree(root);
    }

    private static void printTree(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        printTree(node.getLeft());
        printTree(node.getRight());
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import random

def generate():
    return Node()

class Node:
    def __init__(self, val=1, left=None, right=None):
        self.val = val
        self._left = left
        self._right = right
        self._isLeftEvaluated = False
        self._isRightEvaluated = False
    
    @property
    def left(self):
        if not self._isLeftEvaluated:
            if random.random() < 0.5:
                self._left = Node()
            self._isLeftEvaluated = True
        return self._left
    
    @property
    def right(self):
        if not self._isRightEvaluated:
            if random.random() < 0.5:
                self._right = Node()
            self._isRightEvaluated = True
        return self._right

Complexity

  • ⏰ Time complexity: 
    • Generation: o(1) as the generate function returns the root node in constant time.
    • Evaluation: Each node evaluation is also o(1) as it involves a single probabilistic decision per node.
  • 🧺 Space complexity: o(1) for generating the initial root node. However, in practice, the memory grows as more nodes are probabilistically created upon accessing children.