5 Best Ways to Check if an Array Represents Inorder of Binary Search Tree or Not in Python

Rate this post

πŸ’‘ Problem Formulation: Assessing if an array could be the inorder traversal of a Binary Search Tree (BST) is a common algorithmic problem. Given the array [3,2,5,1,4], the task is to determine if there exists a BST where its inorder traversal yields the given array. The desired output in this case would be False, since the array does not follow the non-decreasing order expected from an inorder traversal of a BST.

Method 1: Check for Non-Decreasing Order

An inorder traversal of a Binary Search Tree always results in a non-decreasing order of values. Therefore, by checking whether the input array is sorted in non-decreasing order, we can verify if it represents the inorder traversal of a BST. This is the most straightforward approach and can be done in linear time O(n).

Here’s an example:

def is_inorder_bst(arr):
    return arr == sorted(arr)

# Example usage
arr = [1, 2, 4, 3, 5]
print(is_inorder_bst(arr))

Output: False

This code defines a function is_inorder_bst() that compares the given array with its sorted version to check if they are identical. If not, the function returns False, indicating the array does not represent the inorder traversal of a BST.

Method 2: Iterative Check

By iteratively comparing each element with its successor, we can ensure each value does not exceed the subsequent value, thus satisfying the inorder traversal property of a BST. This method checks for the sorted property without needing to actually sort the array, enhancing efficiency, especially for large input sizes.

Here’s an example:

def is_inorder_bst_iterative(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

# Example usage
arr = [1, 3, 4, 2, 5]
print(is_inorder_bst_iterative(arr))

Output: False

The is_inorder_bst_iterative function iterates over the array, ensuring that each element is less than or equal to the next. If this condition fails, it immediately returns False. Otherwise the array represents the inorder traversal of a BST.

Method 3: Using Recursion

Recursion can be utilized for a divide-and-conquer strategy, where we recursively check for the non-decreasing order of sub-arrays. This method is elegant but not as optimal as the iterative approach, especially when dealing with large arrays due to increased stack overhead.

Here’s an example:

def check_inorder(start, end, arr):
    if start >= end or start < 0:
        return True
    return arr[start] <= arr[start + 1] and check_inorder(start + 1, end, arr)

# Example usage
arr = [1, 3, 5, 4, 8]
print(check_inorder(0, len(arr) - 1, arr))

Output: False

In this example, the check_inorder function takes the start and end indices, along with the array, and checks recursively if each element is less than or equal to the following one. It is used in the example by providing the range of the entire array.

Method 4: Utilizing a Stack

Using a stack, we can resemble the process of an actual inorder traversal. This simulates the traversal of what would be a binary search tree and verifies the order. While it is more complex than previous methods, it is a closer approximation to how an inorder traversal would work during BST operations.

Here’s an example:

def is_inorder_bst_stack(arr):
    stack = []
    prev = -float('inf')
    for value in arr:
        while stack and stack[-1] < value:
            prev = stack.pop()
        if value < prev:
            return False
        stack.append(value)
    return True

# Example usage
arr = [3, 1, 4, 2, 5]
print(is_inorder_bst_stack(arr))

Output: False

The function is_inorder_bst_stack uses a stack to keep track of the visited nodes and prev variable to check the previous value. If the current value is less than the previous value, the array is not the inorder traversal of a BST.

Bonus One-Liner Method 5: Using Python’s all()

Python’s built-in all() function can be used to concisely check if all elements in an array satisfy a condition. Specifically, we can check if each element is less than its successor. This is a compact and Pythonic way to achieve the check, though it does not offer any performance improvements.

Here’s an example:

arr = [1, 3, 5, 7, 9]
is_inorder = all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))
print(is_inorder)

Output: True

The one-liner uses a generator expression to iterate over the array indices and compares each element to its successor, with the all() function ensuring all comparisons return True. If any comparison fails, all() returns False.

Summary/Discussion

  • Method 1: Straightforward Comparison. Strengths: Simple and easy to understand. Weaknesses: May have additional overhead due to sorting.
  • Method 2: Iterative Check. Strengths: More efficient as it does not sort the array. Weaknesses: Still linear time, might not be ideal for partially sorted segments.
  • Method 3: Using Recursion. Strengths: Divide-and-conquer approach, elegant. Weaknesses: Higher stack overhead, potentially less efficient for larger arrays.
  • Method 4: Utilizing a Stack. Strengths: Mimics actual inorder traversal logic, quite robust. Weaknesses: Greater complexity, harder to understand for beginners.
  • Method 5: Python’s all() Function. Strengths: Concise, Pythonic. Weaknesses: No performance gain over Method 2.