CODEWITHSUNDEEP
avl-tree
kmaci
kmaci

Reputation: 3264

Find next greater element in AVL tree

Let's suppose I have following AVL tree and my task is to find next greater element of given element (i.e. it's 7 for 6). What algorithm can I use?

AVL tree

Upvotes: 1

Views: 2260

Answers (1)

Oni1
Oni1

Reputation: 1505

You walk recursivly through the nodes and if you found i.e. the node 6, then you return deepest left children..

pseudo code:

 function find_bigger_key(key, node):
    if node = null then
      return null
    else if node.key = key then
       return min_node(node)
    else if key < node.key then
       return find_bigger_key(key, node.left)
    else
       return find_bigger_key(key, node.right)

 function min_node(node):
    if node.ltree = null then
      return node
    else
       return min_node(node.ltree)

That is only a example how you could do it, but it depends how your AVLTree object model looks like.

A example implementation in python:

class AVLTree(object):
   def __init__(self, key, ltree=None, rtree=None):
      self.key = key ; self.ltree = ltree ; self.rtree = rtree ;
      # perhaps some other attributes here....

   # some other methods here ...

   def find_bigger_key(self, key):
    if not self: return None
    elif self.key == key:
        if self.rtree:
          return self.rtree.min_node()
        else:
          return None
    elif self.key > key:
        return self.left.find_bigger_key(key)
    else:
        return self.right.find_bigger_key(key)

A example output of python:

>>> # aTree is a avltree object that represents your example
>>> key = 6
>>> found_node = aTree.find_bigger_key(key)
>>> print(found_node)
7
>>> key = 7
>>> found_node = aTree.find_bigger_key(key)
>>> print(found_node)
None

Upvotes: 2

Related Questions