How to search for a node in an AVL tree

AVL trees

AVL trees are self-balancing binary search trees. This means that whenever an imbalanceAn imbalance in a binary search tree happens due to one subtree of a node being heavier than the other subtree. is created via the insertion or deletion of a node(s), these trees can restore the balance.

Note: To learn more about what an AVL tree is, and the different types of imbalances that can arise in them due to the insertion/deletion of a node(s), refer to this link.

This maintenance of balance in an AVL tree allows operations such as insertion, deletion, and searching to run in $O(log(N))$ time. Thus, it makes them much more efficient than simple binary search trees, which take $O(N)$ time in the worst case.

Searching

To search for a node with a particular value $x$ , we start with the root node. We compare the value of this root node with $x$ . If the two are equal, we can return a pointer to this node and conclude that the node has been found. If, however, the two are not equal, we need to check whether $x$ is greater than the value of the root node, or less than it.

If $x$ is greater than the root node's value, then we need to repeat this process for its right subtree. Similarly, if $x$ is less than the root node's value, we need to repeat this process for its left subtree. If we encounter a NULL at any point during this process, we can conclude that there is no node in the AVL tree with a value equal to $x$ . Therefore, we can return NULL as well and end our search.

Example 1: Node being searched for is found

Code example

The search operation in an AVL tree can be implemented both recursively and iteratively. The functions highlighted in the code below implement this operation via both approaches in searchRecursive() and searchIterative(), respectively.

Note: We'll hard-code an AVL tree in the main() function instead of building one via the proper way by doing insertions (and rebalancing). This is done to demonstrate searchRecursive() and searchIterative() at work, in isolation from a proper AVL tree insertion implementation.
To learn more about insertions in an AVL tree, refer to this link.

#include <iostream>
using namespace std;
class Node 
{
  public:
    int value;
  Node * left_child;
  Node * right_child;
  Node() 
  {
    value = 0;
    left_child = NULL;
    right_child = NULL;
  }
  Node(int v) 
  {
    value = v;
    left_child = NULL;
    right_child = NULL;
  }
};
class AVLtree 
{
  public:
    Node * root;
  AVLtree() 
  {
    root = NULL;
  }
 
  int height(Node * r) 
  {
    if (r == NULL)
    {
      return -1;
    }
    else 
    {
      int left_subtree_height = height(r->left_child);
      int right_subtree_height = height(r->right_child);
      if (left_subtree_height > right_subtree_height)
      {
        return (left_subtree_height + 1);
      }
      else 
      {
        return (right_subtree_height + 1);
      }
    }
  }
  int getBalanceFactor(Node * n) 
  {
    if (n == NULL)
    {
      return -1;
    }
    return height(n->left_child) - height(n->right_child);
  }
  Node * rightRotate(Node * x) 
  {
    Node * y = x->left_child;
    Node * T2 = y->right_child;
    // Perform rotation  
    y->right_child = x;
    x->left_child = T2;
    return y;
  }
  Node * leftRotate(Node * x) 
  {
    Node * y = x->right_child;
    Node * T2 = y->left_child;
    // Perform rotation  
    y->left_child = x;
    x->right_child = T2;
    return y;
  }
  Node * searchRecursive(Node* root, int val_to_find)
  {
    if(root == NULL) // NULL encountered (node not found)
    {
      cout << val_to_find << " was Not Found!" << endl ;
      return root;
    }
    if(root->value == val_to_find) // node found
    {
      cout << val_to_find << " was Found!" << endl ;
      return root; 
    }
    else
    {
      if(val_to_find > root->value) // search in right subtree
      {
        return searchRecursive(root->right_child, val_to_find) ;
      }
      else if(val_to_find < root->value) // search in left subtree
      {
        return searchRecursive(root->left_child, val_to_find) ;
      }
    }
  }
  Node* searchIterative(int val_to_find)
  {
    Node* temp = root ;
    while(1)
    {
      if(temp == NULL) // NULL encountered (node not found)
      {
        cout << val_to_find << " was Not Found!" << endl ;
        return NULL ;
      }
      if(temp->value == val_to_find) // node found
      {
        cout << val_to_find << " was Found!" << endl ;
        return temp;
      }
      else
      {
        if(val_to_find > temp->value) // continue searching in right subtree
        {
          temp = temp->right_child ;
        }
        else if(val_to_find < temp->value) // continue searching in left subtree
        {
          temp = temp->left_child ;
        }
      }
    }
  }
};
void prettyPrintTree(Node * r, int space) 
{
  if (r == NULL) 
  {
    return;
  }
  space += 10; 
  prettyPrintTree(r->right_child, space); 
  cout << endl;
  for (int i = 10; i < space; i++) 
  {
    cout << " ";   
  }
  cout << r->value << "\n"; 
  prettyPrintTree(r->left_child, space); 
}
int main()
{
  AVLtree obj;
  //Node n1;
  Node * n1 = new Node();
  //Node n2;
  Node * n2 = new Node();
  //Node n3;
  Node * n3 = new Node();
  //Node n4;
  Node * n4 = new Node();
  //Node n5;
  Node * n5 = new Node();
  //Node n6;
  Node * n6 = new Node();
  n1->value = 20;
  n2->value = 15;
  n3->value = 30;
  n4->value = 10;
  n5->value = 17;
  // First level (root 20):
  obj.root = n1 ;
  // Second level (root 20, left_child 15, right_child 30)
  obj.root->left_child = n2 ;
  obj.root->right_child = n3;
  // Third level (root 15, left_child 10, right_child 17): 
  obj.root->left_child->left_child = n4;
  obj.root->left_child->right_child = n5 ;
  cout << "Tree:" << endl ;
  prettyPrintTree(obj.root , 1);
  cout << endl ;
  cout << "Recursive Search: " ;
  Node * search_result_1 = obj.searchRecursive(obj.root, 17);
  
  cout << "Iterative Search: " ;
  Node * search_result_2 = obj.searchIterative(17);
  
  cout << "Recursive Search: " ;
  Node * search_result_3 = obj.searchRecursive(obj.root, 8);
  
  cout << "Iterative Search: " ;
  Node * search_result_4 = obj.searchIterative(8);
  return 0 ;
}

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

How to search for a node in an AVL tree

AVL trees

Searching

Example 1: Node being searched for is found

Example 2: Node being searched for is not found

Code example

Explanation