☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Requirements needed to construct a unique BT

Medium TUF ID 111 A2Z

Java source ↗ Edit this article ↗

Problem

Someone has a binary tree whose node values are all distinct. They will not show you the tree, only two of its traversals. Which pairs of traversals are guaranteed to determine the tree exactly, so that one and only one binary tree has both of them?

The interview version encodes the traversals as numbers, 1 = preorder, 2 = inorder, 3 = postorder, and asks you to return true when the two given traversal types always identify a unique tree. This article also handles 4 = level order.

Example 1

a = 1 (preorder), b = 2 (inorder)
answer = true          // inorder plus any other traversal is enough

Example 2

a = 1 (preorder), b = 3 (postorder)
answer = false         // two different trees can share both sequences (shown below)

Example 3

a = 2, b = 2
answer = false         // the same traversal twice carries no extra information

This is a concept question: the code is a one-liner, but you are expected to explain why. The rest of the article builds that argument and then checks it by brute force over every small tree.

One traversal is never enough

Fix a shape (where the nodes are, ignoring values). Any traversal visits the nodes of that shape in some fixed order. So if somebody hands you a sequence like [1, 2, 3] and says “this is the preorder”, you can write 1, 2, 3 into the nodes of any shape in preorder order and get a valid tree. Every shape with n nodes produces exactly one tree with that traversal.

The number of shapes with n nodes is the Catalan number: 1, 1, 2, 5, 14, 42, ... for n = 0, 1, 2, 3, 4, 5. So a single traversal of a 5-node tree is consistent with 42 different trees. The Java file verifies this count for every traversal type and every n up to 5.

What each traversal tells you

Rebuilding a tree recursively needs two facts at every step: which value is the root, and which of the remaining values belong to the left subtree. Look at what each traversal offers:

traversal tells you the root? tells you the left/right split?
preorder root, L, R yes, the first value no, the boundary between L and R is invisible
postorder L, R, root yes, the last value no, same reason
level order yes, the first value no, the levels mix both subtrees
inorder L, root, R no yes, once you know the root, everything before it is L

Preorder, postorder and level order all answer the first question and fail the second. Inorder is the mirror image: it cannot name the root by itself, but as soon as somebody else names it, inorder splits the rest of the values perfectly into the left set and the right set. That is why inorder plus any one of the others works, and why no pair without inorder can work.

Once the root and the split are known, the same reasoning repeats inside each subtree. The preorder of the left subtree is the block right after the root; the postorder of the left subtree is the first block; and the level order of the left subtree is the level order of the whole tree filtered to the left values, because BFS visits the left subtree’s nodes depth by depth and left to right, exactly as a BFS of that subtree would. By induction on the number of nodes, the tree is rebuilt uniquely.

The least familiar combination is level order with inorder, so here it is in code. The preorder and postorder versions, which run in O(n) with a hash map, have their own articles.

static TreeNode buildFromLevelAndInorder(List<Integer> level, List<Integer> inorder) {
    if (inorder.isEmpty()) return null;
    int rootVal = level.get(0);
    int split = inorder.indexOf(rootVal);                      // everything before split is in the left subtree
    Set<Integer> leftValues = new HashSet<>(inorder.subList(0, split));
    List<Integer> leftLevel = new ArrayList<>(), rightLevel = new ArrayList<>();
    for (int i = 1; i < level.size(); i++) {
        int v = level.get(i);
        if (leftValues.contains(v)) leftLevel.add(v); else rightLevel.add(v);
    }
    TreeNode root = new TreeNode(rootVal);
    root.left = buildFromLevelAndInorder(leftLevel, inorder.subList(0, split));
    root.right = buildFromLevelAndInorder(rightLevel, inorder.subList(split + 1, inorder.size()));
    return root;
}

The method takes O(n^2) time in the worst case (each level of recursion re-partitions the remaining level-order list), which is fine for explaining the idea. main rebuilds every tree with up to 5 nodes this way and checks the result is identical to the original.

Why preorder and postorder together fail

The smallest counterexample has two nodes. Put 1 at the root and 2 as its only child. Whether the child hangs on the left or on the right:

    1          1
   /            \
  2              2

preorder    [1, 2]       [1, 2]
postorder   [2, 1]       [2, 1]
level order [1, 2]       [1, 2]
inorder     [2, 1]       [1, 2]      <- the only traversal that differs

Preorder, postorder and level order cannot tell a lone left child from a lone right child, because in all three the child is visited on the same side of its parent either way. Only inorder puts the parent between the left side and the right side.

This ambiguity compounds: every node with exactly one child can flip that child to the other side without changing preorder or postorder. A tree with k single-child nodes shares its preorder and postorder with 2^k trees, and a chain of n nodes is the worst case with 2^(n-1). The Java file confirms that number exhaustively for n up to 5.

There is one well-known exception. In a full binary tree (every node has 0 or 2 children), the left child of a root is always the second value of the preorder, and finding it in the postorder reveals where the left subtree ends. So preorder plus postorder is unique for full trees. That is a special case, not the general rule; the experiment checks it for full trees with 1, 3 and 5 nodes.

The rule in code

Put together: the two traversals must be different, and one of them must be inorder.

static boolean canConstructUnique(int a, int b) {
    return a != b && (a == IN || b == IN);
}
  pre in post level
pre no yes no no
in yes no yes yes
post no yes no no
level no yes no no

Checking the rule by brute force

A claim like this is easy to state and easy to get wrong, so the Java file proves it for small trees by trying everything. The experiment needs three pieces.

All shapes. A shape with n nodes is a root plus a left shape of size k and a right shape of size n - 1 - k, for every k. Recursing on that definition lists each shape exactly once.

All labellings. For each shape and each permutation of 1..n, copy the shape and write the permutation into its nodes in preorder. Different shapes give different trees, and the same shape with different permutations gives different trees, so this produces every binary tree on the values 1..n exactly once.

Grouping. For a chosen pair of traversal types, compute both traversals of every tree and use the pair of lists as a hash-map key. If some key collects two or more trees, the pair is ambiguous. The method returns the largest group size; 1 means “always unique”.

static List<Integer> traversal(TreeNode root, int type) {
    List<Integer> out = new ArrayList<>();
    if (type == LEVEL) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            out.add(cur.val);
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
    } else {
        depthFirst(root, type, out);
    }
    return out;
}

static void depthFirst(TreeNode node, int type, List<Integer> out) {
    if (node == null) return;
    if (type == PRE) out.add(node.val);
    depthFirst(node.left, type, out);
    if (type == IN) out.add(node.val);
    depthFirst(node.right, type, out);
    if (type == POST) out.add(node.val);
}

static List<TreeNode> allShapes(int n) {
    List<TreeNode> out = new ArrayList<>();
    if (n == 0) {
        out.add(null);
        return out;
    }
    for (int leftSize = 0; leftSize < n; leftSize++) {
        for (TreeNode left : allShapes(leftSize)) {
            for (TreeNode right : allShapes(n - 1 - leftSize)) {
                TreeNode root = new TreeNode(0);
                root.left = left;
                root.right = right;
                out.add(root);
            }
        }
    }
    return out;
}

/** Copies a shape, writing perm[0], perm[1], ... into its nodes in preorder. */
static TreeNode labelled(TreeNode shape, int[] perm, int[] next) {
    if (shape == null) return null;
    TreeNode node = new TreeNode(perm[next[0]++]);
    node.left = labelled(shape.left, perm, next);
    node.right = labelled(shape.right, perm, next);
    return node;
}

static void permutations(int[] a, int k, List<int[]> out) {
    if (k == a.length) {
        out.add(a.clone());
        return;
    }
    for (int i = k; i < a.length; i++) {
        int t = a[k]; a[k] = a[i]; a[i] = t;
        permutations(a, k + 1, out);
        t = a[k]; a[k] = a[i]; a[i] = t;
    }
}

static boolean isFull(TreeNode node) {
    if (node == null) return true;
    if ((node.left == null) != (node.right == null)) return false;
    return isFull(node.left) && isFull(node.right);
}

/** Over all trees holding the values 1..n, the most distinct trees that share one pair of traversals. 1 means "always unique". */
static int maxTreesSharingTraversals(int n, int a, int b, boolean fullTreesOnly) {
    int[] values = new int[n];
    for (int i = 0; i < n; i++) values[i] = i + 1;
    List<int[]> perms = new ArrayList<>();
    permutations(values, 0, perms);
    Map<List<List<Integer>>, Integer> groups = new HashMap<>();
    int best = 0;
    for (TreeNode shape : allShapes(n)) {
        if (fullTreesOnly && !isFull(shape)) continue;
        for (int[] perm : perms) {
            TreeNode tree = labelled(shape, perm, new int[]{0});
            List<List<Integer>> key = List.of(traversal(tree, a), traversal(tree, b));
            best = Math.max(best, groups.merge(key, 1, Integer::sum));
        }
    }
    return best;
}

For n = 5 there are 42 × 120 = 5040 labelled trees, so all 16 ordered pairs of traversal types are checked in well under a second. main asserts:

Pitfalls