CODEWITHSUNDEEP
algorithminsertbinary-search-treepseudocodeavl-tree
Gabi G
Gabi G

Reputation: 123

An efficient pseudo-code that check if a given BST is a valid AVL tree

I need to write an algorithm (in pseudo-code) that chech if a given BST tree is a valid AVL tree. In doing that I need to give to each node a rank (in AVL trees rank means the height of the node) so the outcome will be a valid AVL tree.

I thought about a simple algorithm that calculates in each step the height of a node and the height of its two sons (if the sons is null then the height is -1), and then checks if the difference between the heights is 1,1 or 1,2 or 2,1. If not then it's not an AVL tree. If yes than we do the same for node.left and node.right.

My problem with that algorithm is that the time complexity is very huge and could go even to O(n^2). Is there a more efficient algorithm?

Another algorithm that I want to find is when given a valid AVL tree and the rank of each node (rank=height), I need to find a series of inserts that build the same tree. I thought about doing it by sorted order of the keys, but the outcome isn't right.

Upvotes: 0

Views: 2210

Answers (1)

user4668606
user4668606

Reputation:

AVL-Tree check

You actually got the right idea. But you missed out on using the recursive definition of the height of a tree

height(node) =  1 + max(height(node.left), height(node.right))

which is why you got an enormous complexity (though O(2^n) is too pessimistic). Instead of directly calculating the height of a node in a top-bottom-approach, you could go the other way and calculate the height of the individual nodes bottom-top:

valid_avl(node):
    if node is null then
        return -1, True

    left_height, left_valid = valid_avl(node.left)
    right_height, right_valid = valid_avl(node.right)

    if not left_valid or not right_valid or abs(left_height - right_height) > 1 then
        return -1, False
    else
        return 1 + max(left_height, right_height), True

You might want to split the this function into two functions and avoid the use of tuples, depending on the language you use. Note that the above is albeit looking similar to python just pseudocode!!!

Rebuilding the tree

This ones actually fairly simple. Get all values in the tree in level-order and insert them exactly in this order. This way the tree never gets rebalanced and each node is automatically placed in the correct position.

Upvotes: 1

Related Questions