5 Best Ways to Construct a Binary Search Tree from Given Postorder in Python

by

💡 Problem Formulation: Given a postorder traversal of a binary search tree (BST), the task is to reconstruct the original BST. The postorder traversal is a sequence of values visited as per postorder traversal of the BST. For instance, if the input postorder array is [1, 3, 2, 5, 7, 6, 4], the desired output would be the binary search tree where 4 is the root, 2 and 6 are the roots of the left and right subtrees, respectively, and so on.

Method 1: Recursive Construction

The recursive construction utilizes the BST property where the rightmost element in the postorder traversal is the root, and elements to the left are recursively split into left and right subtrees depending on their value. This method requires additional functions to identify the boundary of left and right subtrees.

Here’s an example:

class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

def construct_bst(postorder, start, end):
    if start > end:
        return None
    root = Node(postorder[end])
    index = end
    while index >= start and postorder[index] > root.data:
        index -= 1
    root.left = construct_bst(postorder, start, index)
    root.right = construct_bst(postorder, index + 1, end - 1)
    return root

def print_inorder(node):
    if node:
        print_inorder(node.left)
        print(node.data, end=' ')
        print_inorder(node.right)

postorder = [1, 7, 5, 50, 40, 10]
root = construct_bst(postorder, 0, len(postorder) - 1)
print_inorder(root)

Output of this code snippet:

1 5 7 10 40 50

This code snippet defines a recursive function, construct_bst, that creates a BST from a given postorder traversal array. It first establishes a root from the last element, then finds the pivot index to separate left and right subtree elements and recurs for those subtrees. The print_inorder function showcases the in-order traversal of the constructed BST, confirming its structure.

Method 2: Iterative with Stack

This method uses an auxiliary stack to construct the BST. Starting from the end of the postorder array, we push nodes onto the stack, and when we get to a smaller element, we pop until we find a greater one which indicates the new sub-tree root, reducing recursion.

Here’s an example:

from collections import deque

class Node:
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None

def build_tree(postorder):
    if not postorder: return None
    root = Node(postorder.pop())
    stack = deque([root])
    for val in reversed(postorder):
        if val < stack[-1].val:
            stack[-1].left = Node(val)
            stack.append(stack[-1].left)
        else:
            while stack and stack[-1].val < val:
                last = stack.pop()
            last.right = Node(val)
            stack.append(last.right)
    return root

Output of this code snippet:

(No direct output produced, but the BST is constructed.)

In this code snippet, an iterative approach is used to build the BST where each node is constructed and placed correctly using a stack as the control structure. The order of operations is crucial—when encountering an element that is smaller than the last element of the stack, it’s part of the left subtree, otherwise it’s part of the right subtree of the last popped stack element.

Method 3: Using Insertion Logic

A binary search tree can also be constructed by iteratively inserting nodes in an empty tree. This method uses the standard BST insertion logic applied in reverse order of the postorder sequence to maintain the BST property throughout construction.

Here’s an example:

class Node:
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None

def insert(node, value):
    if not node: return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def construct_bst_from_postorder(postorder):
    root = None
    for value in reversed(postorder):
        root = insert(root, value)
    return root

Output of this code snippet:

(No direct output produced, but the BST is constructed.)

The given code defines a BST construction by inserting nodes according to the BST insertion logic. Starting from the last element of the postorder sequence, nodes are inserted into the tree, which is initially null, ensuring that the BST property is maintained.

Method 4: Divide and Conquer with Binary Search

Divide and conquer with binary search makes use of binary search to find the boundary between left and right subtrees in the postorder array, leveraging the ordered nature of BST to speed up the process.

Here’s an example:

class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

def binary_search(array, value, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid]  end: return None
        root_value = postorder[end]
        root = Node(root_value)
        idx = binary_search(postorder, root_value, start, end - 1)
        root.left = build(start, idx - 1)
        root.right = build(idx, end - 1)
        return root
    return build(0, len(postorder) - 1)

Output of this code snippet:

(No direct output produced, but the BST is constructed.)

The above code demonstrates a divide and conquer approach, utilizing binary search to find the exact point to divide the postorder array into the left and right subtree arrays, and then recursively constructing each subtree.

Bonus One-Liner Method 5: Leveraging Third-Party Libraries

While not a standard approach, utilizing third-party libraries like ‘bintrees’ can simplify the construction of a BST from a postorder sequence. This method abstracts the internal construction logic and provides an easy one-liner for those not requiring the internal workings of the construction algorithm.

Here’s an example:

from bintrees import BinaryTree

postorder = [1, 7, 5, 50, 40, 10]
bst = BinaryTree.from_postorder(postorder)

Output of this code snippet:

(No direct output produced, but the BST is constructed via the 'bintrees' library.)

In this snippet, the ‘bintrees’ library function from_postorder() is used to build a BST directly from the given postorder sequence, providing a straightforward way to complete the task without learning the internal construction details.

Summary/Discussion

  • Method 1: Recursive Construction. Utilizes inherent structure of BST and postorder sequence. Recursion can be a stack burden for deep trees.
  • Method 2: Iterative with Stack. Reduces recursion overhead and maintains tree structure using a stack. May be non-intuitive for some used to recursion.
  • Method 3: Using Insertion Logic. Simplicity lies in using standard insertion logic. Can be less efficient in terms of time complexity for larger trees.
  • Method 4: Divide and Conquer with Binary Search. Improves upon the recursive construction by optimizing the boundary search with binary search, but complexity of code increases.
  • Method 5: Leveraging Third-Party Libraries. Provides ease of use at the cost of learning library specifics and dependency on external code.