# Using BST with 2 extra fields using Python

Using Python, another approach to solve the above problem would be to use a simple Binary Search Tree with 2 extra fields:

1. to hold the elements on the left side of a node
2. to store the frequency of element.

In this approach, we traverse the input array from the ending to the begging and add the elements into the BST.
While inserting the elements to the BST, we can compute the number of elements which are lesser elements simply by computing the sum of frequency of the element and the number of elements to the left side of current node, if we are moving to right side of the current node.

Once we place an element in it’s correct position, we can return it’s this sum value

• C++14
• Python

`class` `Node:`

` ` `def` `__init__(` `self` `,val):`

` ` `self` `.val ` `=` `val`

` ` `self` `.left ` `=` `None`

` ` `self` `.right ` `=` `None`

` ` `# denotes number of times (frequency)`

` ` `# an element has occurred.`

` ` `self` `.elecount ` `=` `1`

` ` `# denotes the number of nodes on left`

` ` `# side of the node encountered so far.`

` ` `self` `.lcount ` `=` `0`

`class` `Tree:`

` ` `def` `__init__(` `self` `,root):`

` ` `self` `.root ` `=` `root`

` ` `def` `insert(` `self` `,node):`

` ` `"""This function helps to place an element at`

` ` `its correct position in the BST and returns`

` ` `the count of elements which are smaller than`

` ` `the elements which are already inserted into the BST.`

` ` `"""`

` ` `curr ` `=` `self` `.root`

` ` `cnt ` `=` `0`

` ` `while` `curr!` `=` `None` `:`

` ` `prev ` `=` `curr`

` ` `if` `node.val>curr.val:`

` ` `# This step computes the number of elements`

` ` `# which are less than the current Node.`

` ` `cnt ` `+` `=` `(curr.elecount` `+` `curr.lcount)`

` ` `curr` `=` `curr.right`

` ` `elif` `node.val<curr.val:`

` ` `curr.lcount` `+` `=` `1`

` ` `curr` `=` `curr.left`

` ` `else` `:`

` ` `prev` `=` `curr`

` ` `prev.elecount` `+` `=` `1`

` ` `break`

` ` `if` `prev.val>node.val:`

` ` `prev.left ` `=` `node`

` ` `elif` `prev.val<node.val:`

` ` `prev.right ` `=` `node`

` ` `else` `:`

` ` `return` `cnt` `+` `prev.lcount`

` ` `return` `cnt`

`def` `constructArray(arr,n):`

` ` `t ` `=` `Tree(Node(arr[` `-` `1` `]))`

` ` `ans ` `=` `[` `0` `]`

` ` `for` `i ` `in` `range` `(n` `-` `2` `,` `-` `1` `,` `-` `1` `):`

` ` `ans.append(t.insert(Node(arr[i])))`

` ` `return` `reversed` `(ans)`

`# Driver function for above code `

`def` `main():`

` ` `n ` `=` `7`

` ` `arr ` `=` `[` `10` `, ` `6` `, ` `15` `, ` `20` `, ` `30` `, ` `5` `, ` `7` `]`

` ` `print` `(` `" "` `.join(` `list` `(` `map` `(` `str` `,constructArray(arr,n)))))`

`if` `__name__ ` `=` `=` `"__main__"` `:`

` ` `main()`

`# Code Contributed by Brahmajit Mohapatra`

Output:

3 1 2 2 2 0 0

Time Complexity: O(nLogn)
Auxiliary Space: O(n)