Fullstack Developer

Given an AVL tree, insert an element in the AVL Tree.

An AVL tree is a self-balancing binary search tree.

It has the following properties:

1. It has the property of the binary search tree , i.e for every node , the nodes in its left subtree is less than the node and nodes in the right subtree is greater than the current node.

2. The absolute difference between the height of left subtree and right subtree of any node is less than or equal to 1.

Read more about AVL Tree Here: https://en.wikipedia.org/wiki/AVL_tree

For example:

The numbers in white beside the nodes denote the height of the tree. We can see when we insert 7 in the tree it imbalances the tree at node 10 and hence we do a rotation to rebalance it. FInally we return the in order traversal of the final tree.

Note

1.Do not print anything, just return the root node of the tree.
2.Your constructed tree will be checked by doing an in-order traversal of the tree from the returned root node.

You are given an array 'ARR' of integers of length N. Your task is to find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can have negative numbers as well.

For example, the input [3, 4, -1, 1] should give output 2 because it is the smallest positive number that is missing in the input array.