number of nodes of bst cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
class BST {
private:
Node* root;
public:
BST() {
root = nullptr;
}
Node insert(Node root, int data) {
if (root == nullptr) {
root = new Node(data);
} else {
if (data <= root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
}
return root;
}
int countNodes(Node* root) {
if (root == nullptr) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
int main() {
BST bst;
Node* root = nullptr;
root = bst.insert(root, 10);
bst.insert(root, 5);
bst.insert(root, 15);
bst.insert(root, 3);
bst.insert(root, 7);
bst.insert(root, 12);
bst.insert(root, 18);
int numNodes = bst.countNodes(root);
cout << "Number of nodes in BST: " << numNodes << endl;
return 0;
}
This C++ program creates a Binary Search Tree (BST) structure and counts the number of nodes within the tree. The Node
struct defines the structure of a node in the BST with integer data, left, and right pointers. The BST
class contains functions to insert nodes and count the total number of nodes in the BST.
In the main
function, a BST object bst
is created along with a root
pointer initialized to nullptr
. Nodes with values 10, 5, 15, 3, 7, 12, and 18 are inserted into the BST using the insert
function.
The countNodes
function in the BST
class recursively counts the nodes in the BST. If the current node is nullptr
, it returns 0. Otherwise, it counts the current node and recursively counts nodes in the left and right subtrees, summing up the total count of nodes.
Finally, the program displays the total number of nodes in the BST.