1902. Depth of BST Given Insertion Order

MediumTreeBinary Search TreeBinary TreeOrdered Set

Problem Description

You are given an array order which is a permutation of integers from 1 to n. This array represents the sequence in which nodes are inserted into a binary search tree (BST). The properties of a BST are such that:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

The first element of order is the root of the BST. All subsequent elements are inserted one by one, at the correct position to maintain the BST property. You need to find the depth of this binary search tree, which is the number of nodes along the longest path from the root node down to the farthest leaf node.

Intuition

The intuition behind the solution is to track the depth of the tree while iterating through the order array and inserting elements into the BST. To achieve this efficiently, the solution uses a SortedDict structure, which is a Python data structure that maintains the keys in sorted order and allows binary search operations.

Here's how we use SortedDict to solve the problem:

Initialize the SortedDict with the first element of the order array as the root with a depth of 1 and two sentinel values 0 and infinity with depths 0.
These sentinel values help in finding the lower and higher elements (parent candidates in BST) for the new element to be inserted.
As elements from the order array are processed, determine the depth of the new node by finding the elements just less than (lower) and just greater than (higher) the current element in the sorted keys of the SortedDict.
The depth of the current element will be one more than the maximum depth of the lower or higher neighbors, since it will be the child of one of these neighbors.
Update the maximum depth (ans) if the depth of the current node is greater.
Insert the current element with its computed depth into the SortedDict.
Repeat this process for each element in the order array.
After processing all elements, ans will contain the depth of the binary search tree.

This efficient approach avoids having to build the actual BST and traverse it to find the depth, and instead calculates the depth on-the-fly during insertion.

Learn more about Tree, Binary Search Tree and Binary Tree patterns.

Solution Approach

To understand the implementation of the solution, let's go through the key components of the code:

Data Structure Used

SortedDict: A SortedDict is a data structure in the sortedcontainers library of Python that keeps the keys sorted and allows for binary search. In this scenario, it's being used to keep track of the depth at each inserted node.

Steps of the Algorithm

Initialization: We initiate the SortedDict with a mapping from 0 to depth 0, infinity to depth 0, and the first element of the order array (which is the root node) to depth 1. Both 0 and infinity are sentinel values that assist in determining the depth of the subsequent nodes.
```
sd = SortedDict({0: 0, inf: 0, order[0]: 1})
```

Iterate through order: After the root node is added, we iterate through the remaining numbers in order array. For each number (node) v, we want to find where it fits in the tree and calculate its depth.

for v in order[1:]:  # Skip the first element as it is the root
    ...

Binary Search for Depth: For each number, we perform a binary search (bisect_left(v)) on the SortedDict keys to find the closest smaller value (the predecessor or lower) and the direct successor (higher). These are the two possible parents in the BST.
```
lower = sd.bisect_left(v) - 1
higher = lower + 1
```
Calculate the Depth of the Node: The depth of the new node we are inserting is one more than the maximum depth between its potential parents (lower and higher), this is because in the BST the new node will become the child of one of these nodes.
```
depth = 1 + max(sd.values()[lower], sd.values()[higher])
```
Update the SortedDict and ans: Insert the new node v with its calculated depth into the SortedDict. Also, update ans with the new depth if it is greater than the current maximum depth found.
```
ans = max(ans, depth)
sd[v] = depth
```
Return the Maximum Depth: Once we have inserted all the elements, ans will hold the maximum depth of the tree, which we then return.
```
return ans
```

In this implementation, SortedDict plays a vital role by keeping track of nodes in sorted order and their associated depth, using binary search for neighbor lookup which results in efficient on-the-fly depth computation of the BST while simulating the insertion process.

Time Complexity

The time complexity of this approach is O(n log n), where n is the number of elements in the order array. This is because, for each insertion into the SortedDict, which internally maintains a sorted order, the operations perform in O(log n) time, and we do this for each of the n elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's use a small example with an order array. Suppose our order array is [3, 2, 5, 1, 4]. This represents the sequence in which nodes will be inserted into the BST.

Initialization: We start with our SortedDict initialized as follows:

sd = SortedDict({0: 0, inf: 0, 3: 1})  # Root node '3' with depth '1'
ans = 1  # The depth of the tree

Process Second Element (2):
- Insert '2' into the BST. The closest smaller value to '2' is '0', and the closest larger value is '3'.
- Since the depth of '0' (a sentry) is '0', and the depth of '3' (root node) is '1', the depth of '2' will be one more than the maximum depth of these two nodes, which is 1 + 1 = 2.
Update our SortedDict:
```
sd = SortedDict({0: 0, 2: 2, 3: 1, inf: 0})
ans = 2
```
Process Third Element (5):
- Insert '5' into the BST. The closest smaller value to '5' is '3', and the closest larger is inf.
- The depth of '5' becomes 1 + 1 = 2 (since the depth of '3' is '1').
Update our SortedDict:
```
sd = SortedDict({0: 0, 2: 2, 3: 1, 5: 2, inf: 0})
```
ans remains 2 as we did not find a deeper depth.
Process Fourth Element (1):
- Insert '1'. The closest smaller is '0', and the closest larger is '2'.
- The depth of '1' will then be 1 + 2 = 3 (since the depth of '2' is '2').
Update our SortedDict:
```
sd = SortedDict({0: 0, 1: 3, 2: 2, 3: 1, 5: 2, inf: 0})
ans = 3
```
Update ans since we found a deeper depth.
Process Fifth Element (4):
- Insert '4' into the BST. The closest smaller value is '3', and the closest larger is '5'.
- The depth of '4' is calculated as 1 + 2 = 3 (since both '3' and '5' have a depth of '1' and '2' respectively, and we take the max).
Update our SortedDict:
```
sd = SortedDict({0: 0, 1: 3, 2: 2, 3: 1, 4: 3, 5: 2, inf: 0})
```
ans remains 3 since the depth of '4' matches the current deepest level.
Return the Maximum Depth: After processing all elements, the maximum depth ans is already updated to 3, which is the depth of this BST.

Following this step-by-step illustration, it's clear how the SortedDict and the algorithm work together to insert nodes and compute the depth of the BST efficiently without constructing the actual tree.

Solution Implementation

1from sortedcontainers import SortedDict
2from typing import List
3
4class Solution:
5    def maxDepthBST(self, order: List[int]) -> int:
6        # Create a SortedDict initialized with border elements with depth 0 and 
7        # the root of BST with depth 1
8        sorted_dict = SortedDict({0: 0, float('inf'): 0, order[0]: 1})
9      
10        # Initialize answer with the depth of the first element (root), which is 1
11        max_depth = 1
12      
13        # Iterate over the remaining elements in the order list starting from the second
14        for value in order[1:]:
15            # Find the keys that would be immediate predecessors and successors of the value
16            lower_index = sorted_dict.bisect_left(value) - 1
17            higher_index = lower_index + 1
18          
19            # The new depth is calculated by 1 plus the max depth of immediate lower and higher keys
20            depth = 1 + max(sorted_dict.peekitem(lower_index)[1], sorted_dict.peekitem(higher_index)[1])
21          
22            # Update the answer if the new calculated depth is greater than the previous max depth
23            max_depth = max(max_depth, depth)
24          
25            # Insert the current value with its calculated depth into the sorted dictionary
26            sorted_dict[value] = depth
27      
28        # Finally, return the maximum depth of the binary search tree
29        return max_depth
30

1class Solution {
2    public int maxDepthBST(int[] order) {
3        // TreeMap to store the nodes with their corresponding depths
4        TreeMap<Integer, Integer> depthMap = new TreeMap<>();
5        // Dummy nodes to handle edge cases
6        depthMap.put(0, 0); // Represents the leftmost boundary
7        depthMap.put(Integer.MAX_VALUE, 0); // Represents the rightmost boundary
8        // Initial case: the root node has a depth of 1
9        depthMap.put(order[0], 1);
10        // The starting maximum depth is the depth of the root, which is 1
11        int maxDepth = 1;
12
13        // Iterate over the remaining nodes in the "order" array
14        for (int i = 1; i < order.length; ++i) {
15            int currentValue = order[i];
16            // Find the immediate lower and higher entries in the TreeMap
17            Map.Entry<Integer, Integer> lowerEntry = depthMap.lowerEntry(currentValue);
18            Map.Entry<Integer, Integer> higherEntry = depthMap.higherEntry(currentValue);
19            // Compute the depth of the current node as one plus the maximum of the depths of lower and higher entry
20            int currentDepth = 1 + Math.max(lowerEntry.getValue(), higherEntry.getValue());
21            // Update the maximum depth found so far
22            maxDepth = Math.max(maxDepth, currentDepth);
23            // Insert the current value and its depth into the TreeMap
24            depthMap.put(currentValue, currentDepth);
25        }
26        // Return the maximum depth found
27        return maxDepth;
28    }
29}
30

1#include <map>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7    int maxDepthBST(std::vector<int>& order) {
8        // TreeMap to store the nodes with their corresponding depths
9        std::map<int, int> depthMap;
10        // Dummy nodes to handle edge cases
11        depthMap[0] = 0; // Represents the leftmost boundary
12        depthMap[INT_MAX] = 0; // Represents the rightmost boundary
13        // Initial case: the root node has a depth of 1
14        depthMap[order[0]] = 1;
15        // The starting maximum depth is the depth of the root, which is 1
16        int maxDepth = 1;
17
18        // Iterate over the remaining nodes in the "order" vector
19        for (size_t i = 1; i < order.size(); ++i) {
20            int currentValue = order[i];
21            // Find the immediate lower and higher entries in the map
22            auto lowerEntry = --depthMap.lower_bound(currentValue);
23            auto higherEntry = depthMap.upper_bound(currentValue);
24            // Compute the depth of the current node as one plus the maximum of the depths of lower and higher entry
25            int currentDepth = 1 + std::max(lowerEntry->second, higherEntry->second);
26            // Update the maximum depth found so far
27            maxDepth = std::max(maxDepth, currentDepth);
28            // Insert the current value and its depth into the map
29            depthMap[currentValue] = currentDepth;
30        }
31        // Return the maximum depth found
32        return maxDepth;
33    }
34};
35

1// TreeMap-like structure using a SortedMap interface from external libraries could be used.
2// For the purpose of this question, assuming such an interface exists in the environment.
3// If not, one would need to implement it or use a workaround.
4interface SortedMap<K, V> {
5  get(key: K): V | undefined;
6  set(key: K, value: V): void;
7  lowerEntry(key: K): [K, V] | undefined;
8  higherEntry(key: K): [K, V] | undefined;
9}
10
11// Initialize a TreeMap-like structure to store nodes with their corresponding depths.
12// Assume that an appropriate SortedMap implementation or a suitable external module is available.
13const depthMap: SortedMap<number, number> = new SortedMapImpl();
14
15// Global method to calculate the maximum depth of the binary search tree.
16function maxDepthBST(order: number[]): number {
17  // Insert dummy nodes to handle edge cases.
18  depthMap.set(0, 0); // Represents the left-most boundary.
19  depthMap.set(Number.MAX_SAFE_INTEGER, 0); // Represents the right-most boundary.
20
21  // The root node has an initial depth of 1.
22  depthMap.set(order[0], 1);
23  // The starting maximum depth is the depth of the root node, which is 1.
24  let maxDepth: number = 1;
25
26  // Iterate over the remaining nodes in the "order" array starting from the second element.
27  for (let i = 1; i < order.length; ++i) {
28    let currentValue: number = order[i];
29    // Fetch the immediate lower and higher entries in the TreeMap-like structure.
30    const lowerEntry: [number, number] | undefined = depthMap.lowerEntry(currentValue);
31    const higherEntry: [number, number] | undefined = depthMap.higherEntry(currentValue);
32
33    // If either entry is undefined, use zero as their depth.
34    const lowerDepth: number = lowerEntry?.[1] ?? 0;
35    const higherDepth: number = higherEntry?.[1] ?? 0;
36
37    // Compute the depth of the current node as one plus the maximum of the depths of lower and higher entries.
38    const currentDepth: number = 1 + Math.max(lowerDepth, higherDepth);
39
40    // Update the maximum depth found so far.
41    maxDepth = Math.max(maxDepth, currentDepth);
42  
43    // Insert the current value and its depth into the TreeMap-like structure.
44    depthMap.set(currentValue, currentDepth);
45  }
46
47  // Return the maximum depth found.
48  return maxDepth;
49}
50

Time and Space Complexity

Time Complexity

The time complexity of the maxDepthBST function can be analyzed as follows:

The construction of the initial SortedDict is O(log n) since it involves inserting the first element of order into the data structure.
The main for loop runs for every element in the order list except the first one, which is n - 1 iterations where n is the number of elements in order.
Within the loop, the bisect_left operation performs a binary search which is O(log k) where k is the number of elements in the SortedDict at that point.
The indexing operations to access sd.values()[lower] and sd.values()[higher] are O(1) as SortedDict maintains a list-like values view.
The max and bisect_left operations within the loop are also O(log k).
The update operation sd[v] = depth is O(log k) since it might require rebalancing the tree structure of the SortedDict.

Considering the loop iteration and the operations that occur within each iteration, the total time complexity is O((n - 1) * log k). Since k can be at most n as the loop progresses, this simplifies to O(n log n).

Space Complexity

The space complexity can be analyzed as follows:

The SortedDict can hold up to n + 2 elements (including the added 0 and inf keys).
The depth and ans variables use a constant amount of space.

Therefore, the space complexity is O(n) due to the space required to store the elements in the SortedDict.

In conclusion, the time complexity of the code is O(n log n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know

1902. Depth of BST Given Insertion Order

Problem Description

Intuition

Solution Approach

Data Structure Used

Steps of the Algorithm

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings