1902. Depth of BST Given Insertion Order
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 theorder
array as the root with a depth of1
and two sentinel values0
andinfinity
with depths0
. - 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 theSortedDict
. - The depth of the current element will be one more than the maximum depth of the
lower
orhigher
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 from0
to depth0
,infinity
to depth0
, and the first element of theorder
array (which is the root node) to depth1
. Both0
andinfinity
are sentinel values that assist in determining the depth of the subsequent nodes.1sd = SortedDict({0: 0, inf: 0, order[0]: 1})
-
Iterate through
order
: After the root node is added, we iterate through the remaining numbers inorder
array. For each number (node)v
, we want to find where it fits in the tree and calculate its depth.1for v in order[1:]: # Skip the first element as it is the root 2 ...
-
Binary Search for Depth: For each number, we perform a binary search (
bisect_left(v)
) on theSortedDict
keys to find the closest smaller value (the predecessor orlower
) and the direct successor (higher
). These are the two possible parents in the BST.1lower = sd.bisect_left(v) - 1 2higher = 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
andhigher
), this is because in the BST the new node will become the child of one of these nodes.1depth = 1 + max(sd.values()[lower], sd.values()[higher])
-
Update the
SortedDict
andans
: Insert the new nodev
with its calculated depth into theSortedDict
. Also, updateans
with the new depth if it is greater than the current maximum depth found.1ans = max(ans, depth) 2sd[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.1return 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 EvaluatorExample 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:1sd = SortedDict({0: 0, inf: 0, 3: 1}) # Root node '3' with depth '1' 2ans = 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
:1sd = SortedDict({0: 0, 2: 2, 3: 1, inf: 0}) 2ans = 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
:1sd = SortedDict({0: 0, 2: 2, 3: 1, 5: 2, inf: 0})
ans
remains2
as we did not find a deeper depth. - Insert '5' into the BST. The closest smaller value to '5' is '3', and the closest larger is
-
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
:1sd = SortedDict({0: 0, 1: 3, 2: 2, 3: 1, 5: 2, inf: 0}) 2ans = 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
:1sd = SortedDict({0: 0, 1: 3, 2: 2, 3: 1, 4: 3, 5: 2, inf: 0})
ans
remains3
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 to3
, 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
isO(log n)
since it involves inserting the first element oforder
into the data structure. - The main for loop runs for every element in the
order
list except the first one, which isn - 1
iterations wheren
is the number of elements inorder
. - Within the loop, the
bisect_left
operation performs a binary search which isO(log k)
wherek
is the number of elements in theSortedDict
at that point. - The indexing operations to access
sd.values()[lower]
andsd.values()[higher]
areO(1)
asSortedDict
maintains a list-like values view. - The
max
andbisect_left
operations within the loop are alsoO(log k)
. - The update operation
sd[v] = depth
isO(log k)
since it might require rebalancing the tree structure of theSortedDict
.
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 ton + 2
elements (including the added0
andinf
keys). - The
depth
andans
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node