LeetCode 1902: Depth of BST Given Insertion Order Solution

Master LeetCode problem 1902 (Depth of BST Given Insertion Order), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1902. Depth of BST Given Insertion Order

Medium

Array Tree Binary Search Tree Binary Tree Ordered Set

Problem Explanation

Explanation:

To find the depth of a Binary Search Tree (BST) given its insertion order, we can simulate the insertion process and calculate the depth as we go. We will maintain a variable to track the current depth and update it whenever we insert a new node. We will use a hashmap to store the depth of each node based on its value.

Initialize a hashmap to store the depth of each node.
Initialize a variable maxDepth to store the maximum depth encountered during the insertion process.
Iterate through the insertion order of the BST.
For each value, insert the node into the BST and calculate its depth based on its parent node's depth.
Update the maxDepth if the current node's depth is greater than the maxDepth.
Return the maxDepth as the depth of the BST.

Time Complexity: O(nlogn) where n is the number of nodes in the BST. Space Complexity: O(n) for the hashmap storing the depth of each node.

Solution Code

class Solution {
    public int maxDepthBST(int[] order) {
        Map<Integer, Integer> depthMap = new HashMap<>();
        int maxDepth = 0;
        for (int val : order) {
            int depth = 1;
            if (depthMap.containsKey(val - 1)) {
                depth = depthMap.get(val - 1) + 1;
            }
            depthMap.put(val, depth);
            maxDepth = Math.max(maxDepth, depth);
        }
        return maxDepth;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1902 (Depth of BST Given Insertion Order)?

This page provides optimized solutions for LeetCode problem 1902 (Depth of BST Given Insertion Order) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 1902 (Depth of BST Given Insertion Order) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1902 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1902 in Java, C++, or Python.

Back to LeetCode Solutions