Implement an enhanced Binary Search Tree (BST) that supports complex analytical and structural queries.
The BST must still follow the structural duplicate rule:
This creates right-skewed duplicate chains.
1
2
3
4
5
6
7
n
v1 v2 v3 ... vn
q
query_1
query_2
...
query_q
| Query | Description | Output Format | Special Case |
|---|---|---|---|
DEPTH x |
Return depth of node x (root = 0) | Integer | Not Found if x does not exist |
WIDTH |
Maximum number of nodes at any level | Integer | — |
LONGEST_PATH |
Longest path from root to leaf | v1 -> v2 -> ... -> vk |
Any valid path if multiple |
DELETE x |
Delete first occurrence of x | (No output required) | Value not found |
KTH k |
k-th smallest element (1-based) | Integer | Invalid if k out of range |
RANGE_SUM l r |
Sum of values in range [l, r] | Integer | 0 if no values in range |
LCA x y |
Lowest Common Ancestor of x and y | Integer | Not Found if either node missing |
PATH_SUM x |
Sum from root → node x | Integer | Not Found |
VALIDATE |
Check BST validity (duplicate rule applied) | VALID / INVALID |
— |
PRINT_LEVEL_ZIGZAG |
Zigzag level order traversal | Each level on new line | — |
Example:
1
2
3
4
5
10
/ \
5 20
/ \ / \
4 8 15 25
LCA(4, 8)
The lowest common node is 5
LCA(4, 15)
The lowest common node is 10
This involves traversing the tree in level-order, but with alternating directions between levels.
Example:
1
2
3
4
5
10
/ \
5 20
/ \ /
4 8 15
Normal Order:
1
2
3
10
5 20
4 8 15
ZIGZAG:
1
2
3
10 (->)
20 5 (<-)
4 8 15 (->)
Input 1
1
2
3
4
5
6
7
8
9
10
11
12
10 5 15 3 7 12 18 7 6 8 20 1
8
WIDTH
LONGEST_PATH
KTH 5
RANGE_SUM 5 15
LCA 6 8
PATH_SUM 8
DELETE 7
PRINT_LEVEL_ZIGZAG
Output 1
1
2
3
4
5
6
7
8
9
10
11
4
10 -> 5 -> 7 -> 7 -> 8
7
70
7
37
10
15 5
3 7 12 18
20 8 6 1
7
Input 2
1
2
3
4
5
6
7
8
9
10
11
12
10
8 8 8 8 4 12 2 6 10 14
9
WIDTH
LONGEST_PATH
KTH 3
RANGE_SUM 8 8
LCA 2 14
PATH_SUM 10
DELETE 8
VALIDATE
PRINT_LEVEL_ZIGZAG
Output 2
1
2
3
4
5
6
7
8
9
10
11
12
13
4
8 -> 8 -> 8 -> 8 -> 12 -> 10
6
32
8
54
VALID
8
8
8
8
12 4
2 6 10 14
Implement an AVL Tree that supports dynamic updates and advanced analytical queries.
Your AVL Tree must:
Duplicate vẫn tạo right chain, nhưng AVL sẽ rebalance lại.
AVLNode: Each node must maintain:
1
2
3
4
5
6
7
n
v1 v2 v3 ... vn
q
query_1
query_2
...
query_q
| Query | Description | Output Format | Special Case |
|---|---|---|---|
INSERT x |
Insert value x and rebalance AVL | (No output) | — |
DELETE x |
Delete first occurrence of x using in-order predecessor | (No output) | Value not found |
KTH k |
k-th smallest element (1-based) | Integer | Invalid |
RANK x |
Number of elements ≤ x | Integer | — |
RANGE_SUM l r |
Sum of values in range [l, r] | Integer | 0 if no values |
HEIGHT |
Height of AVL tree | Integer | — |
CHECK_BALANCE |
Verify AVL property (balance factor ∈ {-1,0,1}) | YES / NO |
— |
LCA x y |
Lowest Common Ancestor | Integer | Not Found |
PRINT_LEVEL |
Level-order traversal (BFS) | Each level on new line | — |
Example:
1
2
3
4
5
10
/ \
5 20
/ \ / \
4 8 15 25
LCA(4, 8)
The lowest common node is 5
LCA(4, 15)
The lowest common node is 10
Samples:
1
2
3
4
5
10
/ \
5 20
/ \
3 7
1
2
3
10
5 20
3 7
Input 1:
1
2
3
4
5
6
7
8
9
10
8
10 20 30 40 50 25 5 35
7
KTH 3
RANK 25
RANGE_SUM 10 40
HEIGHT
LCA 5 25
DELETE 30
PRINT_LEVEL
Output 1
1
2
3
4
5
6
7
8
9
20
4
160
3
20
25
20 40
10 35 50
5
Input 2:
1
2
3
4
5
6
7
8
9
10
11
10
15 10 20 8 12 17 25 19 16 18
8
KTH 5
RANK 18
RANGE_SUM 10 20
HEIGHT
LCA 8 12
DELETE 15
CHECK_BALANCE
PRINT_LEVEL
Output 2
1
2
3
4
5
6
7
8
9
10
11
16
7
127
4
10
YES
12
10 20
8 17 25
16 19
18