We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Depth of BST Given Insertion Order

Number: 2052

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an insertion order of distinct integers (a permutation from 1 to n), simulate the insertion process into a binary search tree (BST). The BST is built by inserting the first element as the root and then inserting each subsequent number so that the BST properties hold. Return the depth (i.e. the number of nodes on the longest root-to-leaf path) of the final BST.

Key Insights

  • When inserting a new value into a BST, its depth is determined by the depth of its immediate valid predecessor or successor in the BST.
  • Use an auxiliary sorted container (or ordered set) to quickly locate the nearest inserted numbers (predecessor and successor).
  • The new node’s depth is 1 plus the maximum depth of these two neighboring nodes.
  • The problem can be solved in a single pass by updating the maximum depth as you simulated the insertions.

Space and Time Complexity

Time Complexity: O(n log n) on average with a balanced search approach, though worst-case using a sorted list might lean towards O(n^2) due to insertion costs.
Space Complexity: O(n) for storing the depths and the sorted list of inserted elements.

Solution

The idea is to simulate the BST insertion without explicitly constructing the complete tree structure. We maintain a sorted list (or ordered set) of the elements that have been inserted already along with a mapping from each value to its depth in the BST. For every new element, we determine its position in the sorted list (using binary search) and identify its closest lower and higher neighbors (if they exist). The new element’s depth will be the greater of these neighbors’ depths plus one. By tracking the maximum depth throughout the process, we obtain the final BST depth.

Code Solutions

# Python solution using bisect to maintain a sorted list.
import bisect

def bstInsertionDepth(order):
    # This will serve as our sorted list of inserted elements.
    sorted_list = []
    # Dictionary mapping element to its BST depth.
    depth_map = {}
    max_depth = 0

    for num in order:
        if not sorted_list:
            # First element becomes the root with depth 1
            depth_map[num] = 1
            sorted_list.append(num)
            max_depth = 1
        else:
            # Find the position to insert the current number in sorted_list.
            pos = bisect.bisect_left(sorted_list, num)
            current_depth = 0
            # Check predecessor (largest number less than num)
            if pos > 0:
                pred = sorted_list[pos - 1]
                current_depth = max(current_depth, depth_map[pred])
            # Check successor (smallest number greater than num)
            if pos < len(sorted_list):
                succ = sorted_list[pos]
                current_depth = max(current_depth, depth_map[succ])
            depth_map[num] = current_depth + 1
            bisect.insort(sorted_list, num)
            max_depth = max(max_depth, depth_map[num])
    return max_depth

# Example usage:
print(bstInsertionDepth([2, 1, 4, 3]))  # Output: 3
← Back to All Questions