Code Implementation

class Solution:
    def depthOfBST(self, order):
        def insert(node, val, depth):
            if not node:
                return {'val': val, 'left': None, 'right': None}, depth
            if val < node['val']:
                node['left'], d = insert(node['left'], val, depth + 1)
            else:
                node['right'], d = insert(node['right'], val, depth + 1)
            return node, d

        root = None
        max_depth = 0
        for val in order:
            root, d = insert(root, val, 1)
            max_depth = max(max_depth, d)
        return max_depth
      

class Solution {
public:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int v): val(v), left(nullptr), right(nullptr) {}
    };
    int insert(Node*& node, int val, int depth) {
        if (!node) {
            node = new Node(val);
            return depth;
        }
        if (val < node->val)
            return insert(node->left, val, depth + 1);
        else
            return insert(node->right, val, depth + 1);
    }
    int depthOfBST(vector<int>& order) {
        Node* root = nullptr;
        int maxDepth = 0;
        for (int v : order) {
            int d = insert(root, v, 1);
            if (d > maxDepth) maxDepth = d;
        }
        return maxDepth;
    }
};
      

class Solution {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }
    private int insert(Node node, int val, int depth) {
        if (node == null) {
            return depth;
        }
        if (val < node.val) {
            if (node.left == null) {
                node.left = new Node(val);
                return depth + 1;
            }
            return insert(node.left, val, depth + 1);
        } else {
            if (node.right == null) {
                node.right = new Node(val);
                return depth + 1;
            }
            return insert(node.right, val, depth + 1);
        }
    }
    public int depthOfBST(int[] order) {
        Node root = null;
        int maxDepth = 0;
        for (int v : order) {
            if (root == null) {
                root = new Node(v);
                maxDepth = 1;
            } else {
                int d = insert(root, v, 1);
                if (d > maxDepth) maxDepth = d;
            }
        }
        return maxDepth;
    }
}
      

var depthOfBST = function(order) {
    function insert(node, val, depth) {
        if (!node) return [{ val: val, left: null, right: null }, depth];
        if (val < node.val) {
            let [left, d] = insert(node.left, val, depth + 1);
            node.left = left;
            return [node, d];
        } else {
            let [right, d] = insert(node.right, val, depth + 1);
            node.right = right;
            return [node, d];
        }
    }
    let root = null;
    let maxDepth = 0;
    for (let v of order) {
        let result = insert(root, v, 1);
        root = result[0];
        let d = result[1];
        if (d > maxDepth) maxDepth = d;
    }
    return maxDepth;
};
      

Problem Description

Given an array order representing the insertion order of unique integers into a Binary Search Tree (BST), determine the maximum depth (also known as height) of the BST that would be constructed using this order.

• You must insert the elements from order into the BST one by one, in the given sequence.
• The BST is constructed according to standard rules: for each node, values less than the node go to the left, and greater go to the right.
• Each value in order is unique.
• The output is the maximum depth of the BST after all insertions. The depth of a tree with only a root node is 1.

Thought Process

At first glance, the problem seems to require building an actual BST and then calculating its depth. The brute-force approach would be to construct the tree node by node, and after all insertions, traverse the tree to find its maximum depth.

But since the insertion order is fixed and each insertion can tell us the depth at which the node is added, we can optimize by tracking the depth dynamically while inserting. Each time we insert a new value, we can note the depth at which it was inserted, and keep a running maximum.

This avoids the need for a separate traversal at the end and ensures that we are not doing unnecessary work. The key insight is that the maximum depth is determined by the deepest node encountered during the insertions.

Solution Approach

• Step 1: Define a structure for the BST node (with value, left, and right pointers).
• Step 2: For each value in the order array, insert it into the BST:
  • If the tree is empty, the first value becomes the root (depth 1).
  • For each subsequent value, traverse the tree from the root, comparing values to decide whether to go left or right, incrementing the depth at each level.
  • Insert the new value as a left or right child when a null spot is found, and record the depth at which it was inserted.
• Step 3: After each insertion, update the maximum depth encountered so far.
• Step 4: After all insertions, return the maximum depth found.

This approach ensures that each insertion knows its depth immediately, and we never need to revisit nodes or perform a separate traversal to compute the depth.

Example Walkthrough

Let's use the input order = [4, 2, 6, 1, 3, 5, 7].

1. Insert 4: Tree is empty, so 4 becomes root at depth 1. Max depth = 1
2. Insert 2: 2 < 4, go left. Insert at depth 2. Max depth = 2
3. Insert 6: 6 > 4, go right. Insert at depth 2. Max depth = 2
4. Insert 1: 1 < 4 (left), 1 < 2 (left), insert at depth 3. Max depth = 3
5. Insert 3: 3 < 4 (left), 3 > 2 (right), insert at depth 3. Max depth = 3
6. Insert 5: 5 > 4 (right), 5 < 6 (left), insert at depth 3. Max depth = 3
7. Insert 7: 7 > 4 (right), 7 > 6 (right), insert at depth 3. Max depth = 3

The final BST has maximum depth 3.

Time and Space Complexity

• Brute-force approach: For each insertion, traverse from root to the correct spot (O(height)), and then do a full traversal at the end to compute depth (O(N)). In the worst case (unbalanced), each insertion could be O(N), so total time is O(N²).
• Optimized approach (as above): Each insertion still takes O(height), but we track the depth during insertion, so no need for a full traversal at the end. In the average case (balanced tree), height is O(log N), so total time is O(N log N). In the worst case (degenerated tree), it's O(N²).
• Space complexity: O(N) for the tree nodes.

Summary

The problem asks for the maximum depth of a BST built from a given insertion order. By tracking the depth during each insertion, we efficiently find the answer without needing a separate traversal. The approach is both intuitive and practical, leveraging the BST property and the known order of insertions to optimize the solution.