808. Depth of BST Given Insertion Order
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.
- 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 binary search tree is constructed as follows:
- order[0] will be the root of the binary search tree.
- All subsequent elements are inserted as the child of any existing node such that the binary search tree properties hold.
Return the depth of the binary search tree.
A binary tree's depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: order = [2,1,4,3]
Output: 3
Explanation:
The binary search tree has a depth of 3 with path 2->3->4.
Example 2:
Input: order = [2,1,3,4]
Output: 3
Explanation:
The binary search tree has a depth of 3 with path 2->3->4.
Now Your Turn!
Pick the correct output for the given inputInput: order [3,1,5,2,4]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- n == order.length
- 1 <= n <= 105
- order is a permutation of integers between 1 and n.