CODEWITHSUNDEEP
data-structuresavl-tree
GeekNomore
GeekNomore

Reputation: 23

How to return the leftmost node of AVL tree in O(1) time?

My idea is:

    AVLNode minOfTree(AVLNode node) {
        while (node.left != null) node = node.left;
    return node;
    }

However, a while loop can't be O(1) time right?

Upvotes: 0

Views: 255

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

You are correct. It takes O(log N) time to walk from the root to the left-most node.

So, just keep a pointer the the left-most node around. Whenever you delete it or insert a smaller node, just find the left-most node again. Insert and delete both take O(log N) time already, so you can spend an additional O(log N) time without changing their complexity.

Upvotes: 1

Related Questions