Problem Statement

Given a pair of tree traversal, return true if a unique binary tree can be constructed otherwise false. Each traversal is represented with integer: 1 -> Preorder , 2 -> Inorder , 3 -> Postorder

Examples

Example 1:

Input : 1 2
Output : true 

Explanation : Answer is True.
It is possible to construct a unique binary tree. This is because the preorder traversal provides the root of the tree, and the inorder traversal helps determine the left and right subtrees.

Example 2:

Input : 2 2
Output : false

Explanation : Two inorder traversals are insufficient to uniquely determine a binary tree.

Different Approaches

1️⃣ Hard Code Approach

Intuition:

The concept of "uniqueness" implies that there must be only one binary tree that matches the provided traversal sequences. Without this requirement, multiple trees could fit the same traversals, leading to ambiguity.

Let’s examine the scenarios where two types of traversals—preorder, postorder, and inorder—are given:

Scenario 1: Given Preorder and Postorder Traversal

When provided with just preorder and postorder traversals, it is not possible to uniquely reconstruct a binary tree. This is because multiple trees can produce the same preorder and postorder sequences, leaving room for ambiguity.

Scenario 2: Given Preorder and Inorder Traversal

Preorder traversal starts with the root node and explores the left subtree before the right subtree. This traversal identifies the root and helps in constructing the tree structure. In contrast, inorder traversal processes nodes by visiting the left subtree first, followed by the root, and then the right subtree. This approach clearly separates the left and right subtrees, enabling a unique reconstruction of the binary tree.

Code:

class Solution {
public:
    // Traversal types:
    // 1 = Preorder
    // 2 = Inorder
    // 3 = Postorder
    bool uniqueBinaryTree(int a, int b) {
        // Inorder + Preorder
        if ((a == 1 && b == 2) || (a == 2 && b == 1)) {
            return true;
        }

        // Inorder + Postorder
        if ((a == 2 && b == 3) || (a == 3 && b == 2)) {
            return true;
        }

        // Any other pair → cannot uniquely construct the tree
        return false;
    }
};

Complexity Analysis:

• Time Complexity: The time complexity of this solution is O(1) because it involves only a few constant-time comparisons and logical operations. There are no loops or recursive calls that depend on the input size.
• Space Complexity: The space complexity of this solution is also O(1) since it uses a constant amount of extra space, regardless of the size of the input. The method only involves a few integer variables and does not allocate additional memory based on the input size.