Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Conditions for Unique Tree Construction

MEDIUMProblemSolveExternal Links

Description

Given two types of tree traversals represented as integers, determine whether it is possible to construct a unique binary tree using these two traversals combined.

A binary tree can be traversed in different orders:

  • Preorder (type 1): Visit the root first, then the left subtree, then the right subtree.
  • Inorder (type 2): Visit the left subtree first, then the root, then the right subtree.
  • Postorder (type 3): Visit the left subtree first, then the right subtree, then the root.

Given integers a and b representing two traversal types, return 1 (true) if the combination of these two traversals can always produce a unique binary tree, or 0 (false) if multiple different trees could produce the same pair of traversal sequences.

Two distinct binary trees that produce identical preorder and postorder traversals, demonstrating why certain traversal pairs cannot uniquely determine a tree
Two distinct binary trees that produce identical preorder and postorder traversals, demonstrating why certain traversal pairs cannot uniquely determine a tree

Examples

Example 1

Input: a = 1, b = 2

Output: 1

Explanation: Traversal type 1 is Preorder and type 2 is Inorder. Given both a preorder sequence and an inorder sequence of a binary tree, we can always reconstruct the unique original tree. Preorder tells us the root of every subtree (it appears first), and inorder tells us which nodes belong to the left versus right subtree. Together, every node placement is uniquely determined.

Example 2

Input: a = 1, b = 3

Output: 0

Explanation: Traversal type 1 is Preorder and type 3 is Postorder. These two traversals cannot always uniquely determine a binary tree. Consider a tree with root A and left child B versus a tree with root A and right child B. Both trees produce Preorder = [A, B] and Postorder = [B, A]. Since neither traversal separates left from right, we cannot decide if B is the left or the right child.

Example 3

Input: a = 2, b = 3

Output: 1

Explanation: Traversal type 2 is Inorder and type 3 is Postorder. Inorder combined with Postorder can uniquely construct a binary tree. Postorder gives us the root of each subtree (it appears last in the sequence), and Inorder separates nodes into left and right partitions. This combination fully determines the tree structure, just like Inorder + Preorder does.

Constraints

  • 1 ≤ a, b ≤ 3

Editorial

Brute Force

Intuition

Since there are only three traversal types (Preorder, Inorder, Postorder) and each of the two inputs can be any of these three, there are exactly 3 × 3 = 9 possible input combinations. We can precompute the answer for every possible pair and store them in a lookup table.

Think of it like creating a reference chart before an exam. You list every possible question-and-answer pair ahead of time. When a question arrives, you simply look it up in your chart rather than reasoning from scratch. For 9 pairs, this is perfectly feasible.

The known results from tree theory are:

  • Same traversal twice (e.g., Preorder + Preorder): Always false — a single traversal type cannot uniquely determine a tree.
  • Preorder + Inorder or Postorder + Inorder: Always true — Inorder separates left from right subtrees, and the other traversal identifies roots.
  • Preorder + Postorder: Always false — neither traversal separates left from right subtrees.

Step-by-Step Explanation

Let's trace through with input a = 1 (Preorder), b = 3 (Postorder).

We first build the complete truth table of all 9 traversal pairs:

Step 1: Set up a 3×3 table. Rows represent the first traversal (a), columns represent the second traversal (b). Each cell will hold 0 (not unique) or 1 (unique).

Step 2: Fill cell (Pre, Pre): Two copies of the same traversal. Multiple trees can share the same preorder sequence — for instance, a tree with root A and only a left child B has the same preorder [A, B] as the tree with root A and only a right child B. Mark (1,1) = 0.

Step 3: Fill cell (Pre, In): Preorder gives us the root (first element), and Inorder tells us which nodes belong to the left vs right subtree. Together they uniquely pin down every node. Mark (1,2) = 1.

Step 4: Fill cell (Pre, Post): Preorder gives root first, Postorder gives root last, but neither tells us the left-right partition. Trees A→leftB and A→rightB produce identical Pre=[A,B] and Post=[B,A]. Mark (1,3) = 0.

Step 5: Fill cell (In, Pre): Same analysis as (Pre, In) — the order of the pair does not matter. Inorder still separates left and right, Preorder still identifies roots. Mark (2,1) = 1.

Step 6: Fill cell (In, In): Same traversal twice — no new information. Different tree structures can produce the same inorder sequence. Mark (2,2) = 0.

Step 7: Fill cell (In, Post): Postorder's last element identifies the root, and Inorder separates left from right. This combination uniquely determines the tree. Mark (2,3) = 1.

Step 8: Fill cell (Post, Pre): Same issue as (Pre, Post) — neither traversal provides the left-right split. Mark (3,1) = 0.

Step 9: Fill cell (Post, In): Same as (In, Post). Mark (3,2) = 1.

Step 10: Fill cell (Post, Post): Same traversal twice. Mark (3,3) = 0.

Step 11: Look up our input: row a=1 (Preorder), column b=3 (Postorder) → table[1][3] = 0.

Result: Return 0. Preorder + Postorder cannot uniquely construct a binary tree.

Truth Table — All 9 Traversal Pair Outcomes — Watch as we fill a 3×3 truth table for every possible pair of traversals. Each cell answers: can these two traversals uniquely construct a binary tree?

Algorithm

  1. Create a 4×4 boolean lookup table (indices 0-3, where index 0 is unused)
  2. Precompute the answer for all 9 valid combinations:
    • Same traversal type → false
    • One is Inorder and the other is different → true
    • Neither is Inorder and they differ → false
  3. For input (a, b), return table[a][b]

Code

class Solution {
public:
    bool isPossible(int a, int b) {
        // Pre-computed truth table for all traversal pairs
        // Index: 0=unused, 1=Preorder, 2=Inorder, 3=Postorder
        bool table[4][4] = {
            {false, false, false, false},
            {false, false, true, false},   // Pre + {Pre, In, Post}
            {false, true, false, true},    // In + {Pre, In, Post}
            {false, false, true, false}    // Post + {Pre, In, Post}
        };
        return table[a][b];
    }
};
class Solution:
    def isPossible(self, a: int, b: int) -> bool:
        # Pre-computed truth table for all traversal pairs
        # Index: 0=unused, 1=Preorder, 2=Inorder, 3=Postorder
        table = [
            [False, False, False, False],
            [False, False, True, False],   # Pre + {Pre, In, Post}
            [False, True, False, True],    # In + {Pre, In, Post}
            [False, False, True, False]    # Post + {Pre, In, Post}
        ]
        return table[a][b]
class Solution {
    public boolean isPossible(int a, int b) {
        // Pre-computed truth table for all traversal pairs
        // Index: 0=unused, 1=Preorder, 2=Inorder, 3=Postorder
        boolean[][] table = {
            {false, false, false, false},
            {false, false, true, false},   // Pre + {Pre, In, Post}
            {false, true, false, true},    // In + {Pre, In, Post}
            {false, false, true, false}    // Post + {Pre, In, Post}
        };
        return table[a][b];
    }
}

Complexity Analysis

Time Complexity: O(1)

The lookup table is a fixed 4×4 array. Accessing table[a][b] takes constant time regardless of input values. The table itself is also built in constant time since it has a fixed 16 entries.

Space Complexity: O(1)

The 4×4 boolean table has a fixed size of 16 entries. This does not grow with any input parameter, so the auxiliary space is constant.

Why This Approach Is Not Efficient

While the brute force lookup table runs in O(1) time and O(1) space — which is already optimal for this problem's constraints — it has a significant educational and architectural drawback: it memorizes outcomes without understanding the underlying principle.

The lookup table hard-codes 9 specific results. If we ever needed to extend this to include additional traversal types (such as Level-order as type 4, or Diagonal traversal as type 5), we would need to manually determine and hard-code the result for every new pair. For n traversal types, this requires n² entries, each needing individual verification.

More importantly, the brute force approach does not reveal why certain pairs work and others don't. A student who memorizes the table still cannot answer: "What property makes Inorder special?" or "Would this work with a new traversal type?"

The key insight the brute force misses: there is a single, elegant principle governing all traversal pairs. Understanding this principle eliminates the need for any memorization and provides a one-line solution that generalizes to any number of traversal types.

Optimal Approach - Inorder Separation Principle

Intuition

To uniquely reconstruct a binary tree from two traversal sequences, we need two pieces of information at every recursive step:

  1. Which node is the root of the current subtree.
  2. Which nodes belong to the left subtree and which belong to the right subtree.

Let's examine what each traversal type provides:

  • Preorder (Root → Left → Right): The first element in a preorder sequence is always the root of that subtree. So Preorder gives us the root identity. But it interleaves left and right subtree nodes — we cannot tell where the left subtree ends and the right subtree begins.

  • Postorder (Left → Right → Root): The last element is always the root. Like Preorder, it identifies the root but interleaves left and right subtree nodes.

  • Inorder (Left → Root → Right): The root appears between the left and right subtree nodes. Once we know which element is the root (from Preorder or Postorder), everything to the left of the root in the Inorder sequence belongs to the left subtree, and everything to the right belongs to the right subtree. Inorder is the only standard traversal that cleanly separates left from right.

This leads to the fundamental principle: a unique binary tree can be constructed if and only if one of the two traversals is Inorder (and the two traversals are of different types). Inorder provides the left-right partition that no other traversal can.

Step-by-Step Explanation

Let's verify this principle for input a = 1 (Preorder), b = 2 (Inorder) → expected output: 1 (unique).

We demonstrate WHY Preorder + Inorder uniquely determines a tree by reconstructing one:

Given:

  • Preorder: [1, 2, 4, 5, 3, 6, 7]
  • Inorder: [4, 2, 5, 1, 6, 3, 7]

Step 1: Preorder visits Root → Left → Right, so preorder[0] = 1 is the root of the entire tree. This is our first definite placement.

Step 2: Find 1 in the Inorder sequence at position 3. Everything LEFT of position 3 in Inorder — [4, 2, 5] — belongs to the left subtree. Everything RIGHT — [6, 3, 7] — belongs to the right subtree. This split is only possible because of Inorder.

Step 3: Left subtree has 3 nodes. The next 3 Preorder elements are [2, 4, 5]. First element 2 is the root of the left subtree.

Step 4: Find 2 in the left Inorder [4, 2, 5] at position 1. Left of 2: [4] (one node → leaf). Right of 2: [5] (one node → leaf).

Step 5: Node 4 is the only element in the left partition of node 2 → it must be the left child. Placement is forced.

Step 6: Node 5 is the only element in the right partition of node 2 → it must be the right child. Left subtree of root 1 is complete.

Step 7: Right subtree has 3 nodes. Preorder elements [3, 6, 7]. First element 3 is the root of the right subtree.

Step 8: Find 3 in the right Inorder [6, 3, 7] at position 1. Left: [6], Right: [7]. Both are single elements.

Step 9: Node 6 → left child of 3. Node 7 → right child of 3. Right subtree is complete.

Step 10: The entire tree is uniquely determined. At every step, Preorder told us WHICH node is the root, and Inorder told us WHICH nodes go left vs right. Without Inorder, this separation is impossible.

Optimal check: Is either a or b equal to 2 (Inorder)? b = 2 → yes. Are they different? 1 ≠ 2 → yes. Return 1.

Unique Tree Reconstruction — Why Inorder Is Essential — Watch how Preorder identifies each subtree's root while Inorder separates left from right children, uniquely determining every node placement.

Algorithm

  1. Check if either traversal type is Inorder (value 2):
    • If a == 2 OR b == 2 → at least one traversal can separate left from right subtrees
  2. Check if the two traversals are of different types:
    • If a ≠ b → we have two distinct information sources
  3. If BOTH conditions are satisfied, return true (unique construction is possible)
  4. Otherwise, return false

Code

class Solution {
public:
    bool isPossible(int a, int b) {
        // Unique construction requires:
        // 1. One traversal must be Inorder (type 2) — it separates left/right
        // 2. The two traversals must be different types
        return (a == 2 || b == 2) && (a != b);
    }
};
class Solution:
    def isPossible(self, a: int, b: int) -> bool:
        # Unique construction requires:
        # 1. One traversal must be Inorder (type 2) — it separates left/right
        # 2. The two traversals must be different types
        return (a == 2 or b == 2) and a != b
class Solution {
    public boolean isPossible(int a, int b) {
        // Unique construction requires:
        // 1. One traversal must be Inorder (type 2) — it separates left/right
        // 2. The two traversals must be different types
        return (a == 2 || b == 2) && (a != b);
    }
}

Complexity Analysis

Time Complexity: O(1)

The solution performs exactly two comparisons (check if Inorder is present, check if types differ) and one logical AND. All operations are constant time, independent of any input size.

Space Complexity: O(1)

No additional data structures are used. The solution returns the result of a single boolean expression, requiring zero auxiliary space.