给定一个二叉搜索树的 根节点，我们需要将一个具有给定值的新节点插入到该 BST 中。二叉搜索树中的所有节点都具有不同的值，并且我们可以假设待插入的新值不存在于当前的 BST 中。
示例：
新的键值会被插入到能够维持 BST 性质的位置上。我们从根节点开始，向下移动：如果键值较小，则向左走；如果较大，则向右走。我们持续这一过程，直到找到一个未被占据的位置，该位置可以在不违反 BST 性质的情况下放置节点，然后将其作为新的叶子节点插入。
使用递归在二叉搜索树中插入：
C++
CODEBLOCK_a408204a
C
//Driver Code Starts
#include
#include
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function prototypes
struct Node* newNode(int val);
struct Node insert(struct Node root, int key);
void levelOrder(struct Node* root);
int getHeight(struct Node* root, int h);
// Queue node for level order traversal
struct QueueNode {
struct Node* node;
int level;
struct QueueNode* next;
};
// Queue structure
struct Queue {
struct QueueNode* front;
struct QueueNode* rear;
};
// Create a new queue
struct Queue* createQueue() {
struct Queue q = (struct Queue)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
// Enqueue node with level
void enqueue(struct Queue q, struct Node node, int level) {
struct QueueNode temp = (struct QueueNode)malloc(sizeof(struct QueueNode));
temp->node = node;
temp->level = level;
temp->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
// Dequeue node
struct QueueNode dequeue(struct Queue q) {
if (q->front == NULL)
return NULL;
struct QueueNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
return temp;
}
// Check if queue is empty
int isEmpty(struct Queue* q) {
return q->front == NULL;
}
// Function to get height of tree
int getHeight(struct Node* root, int h) {
if (root == NULL)
return h – 1;
int leftH = getHeight(root->left, h + 1);
int rightH = getHeight(root->right, h + 1);
return (leftH > rightH ? leftH : rightH);
}
// Level order traversal (prints N for null)
void levelOrder(struct Node* root) {
if (root == NULL)
retu