Binary Tree Inversions
mediumSave
Binary TreeDepth-First SearchRecursionTree
Given a binary tree, write a function that returns the number of inversions in the tree. An inversion is defined as a pair of nodes where the ancestor node has a greater value than its descendant node.
Example 1
Input
[ [ 10, 5, 15, 2, 7, null, 18 ] ]
Output
3
Explanation. There are three inversions: 10 > 5, 10 > 2, 10 > 7.
Example 2
Input
[ [ 3, 2, 5, 1, null, 4, 6 ] ]
Output
2
Explanation. There are two inversions: 3 > 1 and 3 > 2.
Example 3
Input
[ [ 1, 2, 3, 4, 5, 6, 7 ] ]
Output
0
Explanation. There are no inversions as the tree is a perfect increasing sequence.
Example 4
Input
[ [ 7, 7, 7, 7, 7 ] ]
Output
0
Explanation. All elements being equal, there are no inversions.
Follow-up: Can you optimize your solution to run in better than O(n^2) time complexity, where n is the number of nodes?
Constraints:
The tree will have at least one node and at most 1000 nodes. Each node's value will be an integer between 1 and 10,000.
- Views
- 3