How hard is LeetCode 1902. Depth of BST Given Insertion Order?

LeetCode 1902. Depth of BST Given Insertion Order is rated Medium on LeetCode.

What is the time complexity of LeetCode 1902. Depth of BST Given Insertion Order?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1902. Depth of BST Given Insertion Order?

The Python solution on this page uses O(h) auxiliary space.

What topics does LeetCode 1902. Depth of BST Given Insertion Order cover?

LeetCode 1902. Depth of BST Given Insertion Order is tagged Tree, Binary Search Tree, Array, Binary Tree and Ordered Set on LeetCode.

Is LeetCode 1902. Depth of BST Given Insertion Order a premium problem?

Yes. LeetCode 1902. Depth of BST Given Insertion Order is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Depth of BST Given Insertion Order — LeetCode 1902 Python Solution

MediumLeetCode PremiumTreeBinary Search TreeArrayBinary TreeOrdered Set

Problem: #1902
Pattern: Tree Traversal
Reading time: 2 min
Source: leetcode.com

The problem

You are given a 0-indexed integer array order of length n, a permutation of integers from 1 to n representing the order of insertion into a binary search tree. A binary search tree is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key.

Example

Input: order = [2,1,4,3]
Output: 3
Explanation: The binary search tree has a depth of 3 with path 2->3->4.

Python solution

Python

class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        sd = SortedDict({0: 0, inf: 0, order[0]: 1})
        ans = 1
        for v in order[1:]:
            lower = sd.bisect_left(v) - 1
            higher = lower + 1
            depth = 1 + max(sd.values()[lower], sd.values()[higher])
            ans = max(ans, depth)
            sd[v] = depth
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(h) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1902. Depth of BST Given Insertion Order is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree, Binary Tree and Binary Search Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1902. Depth of BST Given Insertion Order?: LeetCode 1902. Depth of BST Given Insertion Order is rated Medium on LeetCode.
What is the time complexity of LeetCode 1902. Depth of BST Given Insertion Order?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1902. Depth of BST Given Insertion Order?: The Python solution on this page uses O(h) auxiliary space.
What topics does LeetCode 1902. Depth of BST Given Insertion Order cover?: LeetCode 1902. Depth of BST Given Insertion Order is tagged Tree, Binary Search Tree, Array, Binary Tree and Ordered Set on LeetCode.
Is LeetCode 1902. Depth of BST Given Insertion Order a premium problem?: Yes. LeetCode 1902. Depth of BST Given Insertion Order is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.