Sprawdź poprawność drzewa wyszukiwania binarnego

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem

In Sprawdź poprawność drzewa wyszukiwania binarnego problem podaliśmy korzeń a drzewo, musimy sprawdzić, czy jest to drzewo wyszukiwania binarnego, czy nie.

Przykład:

szpilka

Wyjście:

prawdziwy

Wyjaśnienie: Podane drzewo jest binarnym drzewem wyszukiwania, ponieważ wszystkie elementy pozostawione w każdym poddrzewie są mniejsze niż korzeń poddrzewa. Wszystkie elementy, które mają prawo do każdego poddrzewa, są większe niż katalog główny poddrzewa, a każde poddrzewo samo w sobie jest binarnym drzewem wyszukiwania.

Podejście

• Po pierwsze, robimy w porządku przejście danego drzewa i przechowuj je w pliku szyk. Następnie sprawdzamy, czy tablica jest posortowana w kolejności rosnącej. Następnie mówimy, że jest to drzewo wyszukiwania binarnego, w przeciwnym razie nie jest drzewem wyszukiwania binarnego.
• Aby zminimalizować wykorzystanie przestrzeni pomocniczej, możemy śledzić poprzednio odwiedzany węzeł i jeśli bieżący węzeł jest mniejszy niż poprzedni, to nie jest drzewo wyszukiwania binarnego a jeśli wszystkie poprzednie węzły są mniejsze niż węzeł bieżący, to jest to drzewo wyszukiwania binarnego.
• Możemy uniknąć użycia dodatkowej przestrzeni, przekazując poprzedni węzeł jako parametr.

Kod C ++ dla walidacji drzewa wyszukiwania binarnego

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(3); 
  root->left	 = new Node(2); 
  root->right	 = new Node(5); 
  root->left->left = new Node(1); 
  root->left->right = new Node(4); 

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
} 

Kod Java do walidacji drzewa wyszukiwania binarnego

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
} 

Not a BST

Złożoność czasowa

Na) ponieważ przechodzimy przez każdy węzeł tylko raz.

Złożoność przestrzeni

Na) ponieważ przechowujemy każdy przemierzany węzeł i sprawdzamy, czy tablica jest posortowana w kolejności rosnącej, aby sprawdzić, czy drzewo jest drzewem wyszukiwania binarnego, czy nie.

Referencje