C language method analysis for determining whether a binary tree is a binary search tree

  • 2020-06-07 05:00:46
  • OfStack

An example of C language is given to determine whether a two-tree is a two-tree search tree. To share for your reference, specific as follows:

The problem

Given a two-tree, determine if the two-tree is a two-tree search tree (Binary Search Tree)?

Solution 1: Violent search

Let's first explain the difference between a two-tree and a two-tree search. A two-tree is a tree structure in which each node has at most two children; A two-pronged search tree is a two-pronged tree, but it has additional constraints, which must be true for each node:

All the nodes in the left subtree of node node are less than the value of node. All nodes in the right subtree of node node are greater than the value of node. The left and right subtrees of node node must also be two-pronged search trees.

This is a question that may come up a lot in interviews, but it's a question of understanding the definition of a two-pronged search tree. At first glance, you might want to do this:

[

Assume the current node value is k. For each node in the 2-tree, determine whether the value of its left child is less than k and the value of its right child is greater than k. If all nodes satisfy this condition, then the 2-branch tree is a 2-branch search tree.

]

Unfortunately, this algorithm is wrong. Consider the following two-tree, which fits the criteria of the above algorithm, but is not a two-tree search tree.

[

10
/ \
5 15 -------- binary tree (1)
/ \
6 20

]

So, according to the definition of a two-pronged search tree, we can think of a violent search method to determine whether a two-pronged search tree is a two-pronged search tree.

[

Assume the current node value is k. For each node in the 2-tree, the value of all nodes in its left subtree must be less than k, and the value of all nodes in its right subtree must be greater than k.

]

The code for the brute force search algorithm is as follows. It's not very efficient, but it does get the job done. The worst-case complexity of the solution is O(n^2), and n is the number of nodes. (Worst case when all nodes are on one side)


/* Determine whether all nodes of the left subtree are less than val*/
bool isSubTreeLessThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data < val &&
     isSubTreeLessThan(p->left, val) &&
     isSubTreeLessThan(p->right, val));
}
/* Determine whether all nodes in the right subtree are greater than or not val*/
bool isSubTreeGreaterThan(BinaryTree *p, int val)
{
 if (!p) return true;
 return (p->data > val &&
     isSubTreeGreaterThan(p->left, val) &&
     isSubTreeGreaterThan(p->right, val));
}
/* determine 2 Is a fork tree 2 Fork search tree */
bool isBSTBruteForce(BinaryTree *p)
{
 if (!p) return true;
 return isSubTreeLessThan(p->left, p->data) &&
     isSubTreeGreaterThan(p->right, p->data) &&
     isBSTBruteForce(p->left) &&
     isBSTBruteForce(p->right);
}

A similar solution is as follows: for node node, determine whether the maximum value of its left subtree is greater than the value of node. If so, the 2-branch tree is not a 2-branch search tree. If not, it then determines whether the minimum value of the right subtree is less than or equal to the value of node; if so, it is not a two-pronged search tree. If not, then recursively determine if the left and right subtrees are two-pronged search trees. (The functions of maxValue and minValue in the code return the maximum and minimum values in the 2-cross tree respectively. Here, it is assumed that the 2-cross tree is a 2-cross search tree, and the actual returned values are the maximum and minimum values.)


int isBST(struct node* node)
{
 if (node==NULL) return(true);
 // If the left subtree is the maximum >= The current node Is the value of false
 if (node->left!=NULL && maxValue(node->left) >= node->data)
  return(false);
 //  If the right subtree is minimum <= The current node Value of, return false
 if (node->right!=NULL && minValue(node->right) <= node->data)
  return(false);
 //  If the left subtree or the right subtree is not BST To return to false
 if (!isBST(node->left) || !isBST(node->right))
  return(false);
 //  Pass all tests, return true
 return(true);
}

Solution 2: A better solution

As mentioned earlier binary tree(1) So for example, when we go from node 10 to the right node 15, we know that the right subtree must be somewhere between 10 and +INFINITY. When we go to the left child of 15, 6, we know that the left subtree of 15 has to be somewhere between 10 and 15. Obviously, node 6 doesn't qualify, so it's not a two-fork search tree. The algorithm code is as follows:


int isBST2(struct node* node)
{
   return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
 A given 2 Tree is BST It returns true And its value  >min  As well as  < max.
*/
int isBSTUtil(struct node* node, int min, int max)
{
   if (node==NULL) return(true);
   //  If not min and max Constraint, return false
   if (node->data<=min || node->data>=max) return(false);
   //  Recursively determine if the left and right subtrees satisfy min and max The constraint 
   return
     isBSTUtil(node->left, min, node->data) &&
     isBSTUtil(node->right, node->data, max)
   );
}

Since this algorithm only needs to visit each node once, the time complexity is O(n), which is much more efficient than solution 1.

Solution 3: Middle order traversal algorithm

Since the nodes of a two-pronged search tree are sorted from small to large after traversal, the following solution is given. The time complexity of the solution is also O(n).


bool isBSTInOrder(BinaryTree *root)
{
 int prev = INT_MIN;
 return isBSTInOrderHelper(root, prev);
}
/* Function judgment 2 tree p Whether it is 1 tree 2 Cross search tree, and its node value is greater than prev*/
bool isBSTInOrderHelper(BinaryTree *p, int& prev)
{
 if (!p) return true;
 if (isBSTInOrderHelper(p->left, prev)) { //  If the left subtree is 2 Cross search tree, and node values are greater than prev
  if (p->data > prev) { // Determine whether the current node value is greater than prev Because at this point prev Has been set to the maximum number of nodes that have been traversed in order. 
   prev = p->data;
   return isBSTInOrderHelper(p->right, prev); // If the node value is greater than prev , the setting prev Is the current node value, and determine whether the right subtree is 2 Cross search tree and node values are all greater than prev . 
  } else {
   return false;
  }
 }
 else {
  return false;
 }
}

I hope this article has been helpful in C language programming.


Related articles: