##

##

## Approach

The approach considers traversing the given binary search tree in any of the defined tree traversal orders and printing all the odd nodes of the given binary search tree. In this approach, we have used inorder tree traversal and checked for the node, if the node is odd, then print that node, else continue checking the other nodes.

### Algorithm

**Step 1**. Create a class ‘Node’ which will contain three public members, first will be the integer variable ‘data’, which will contain the value of the node, second will be the ‘node’ variable ‘left’, which will contain the pointer to the left node of that particular node, and third will be the the ‘node’ variable ‘right’, which will contain the pointer to the right node of that particular node.

**Step 2**. Create an ‘insert’ function which will be used to insert nodes in the binary search tree, in this function, check for the node, if the node is NULL, then create the node and return that node, if it is node equal to NULL, then call the ‘insert’ function according to the value received to the value of the node satisfying the condition of BST.

**Step 3**. Create a function ‘getResult()’ that will accept one parameter, i.e., one pointer to the root of the binary search tree.

**Step 4**. In this ‘getResult()’ function, if the root is not NULL, then traverse the tree in ‘inorder’ manner, and print the value of the node if the value of that node is odd.

### C++ Solution

```
#include <bits/stdc++.h>
using namespace std;
// Node Class
class Node
{
public:
int data;
Node *left, *right;
};
// For newnode
Node* newNode(int x)
{
Node* temp = new Node;
temp -> data = x;
temp -> left = temp -> right = NULL;
return temp;
}
// Construct BST
Node* insert(Node* node, int key)
{
// Base case
if (node == NULL)
{
return newNode(key);
}
// Condition of BST
if (key < node->data)
{
node -> left = insert(node -> left, key);
}
else
{
node -> right = insert(node -> right, key);
}
return node;
}
// Function to print all odd nodes
void getResult(Node* root)
{
if (root != NULL)
{
getResult(root -> left);
// If the root’s value is odd, then print the root node
if (root -> data % 2 != 0)
{
cout << root -> data << ", ";
}
getResult(root->right);
}
}
// Driver Code
int main()
{
Node* root = NULL;
root = insert(root, 14);
root = insert(root, 16);
root = insert(root, 47);
root = insert(root, 3);
root = insert(root, 45);
root = insert(root, 6);
root = insert(root, 7);
cout << "All the odd nodes in this binary search tree are:- ";
getResult(root);
return 0;
}
```

**Output:**

```
Output :
All the odd nodes in this binary search tree are:- 3, 7, 45, 47,
```

#### Complexity Analysis

**Time Complexity: **O(N)

Incall to ‘getResult()’, we are traversing the binary search tree using inorder tree traversal and checking all nodes at most once, therefore, the overall time complexity is O(N), where ‘N’ is the total number of nodes in the binary search tree.

**Space Complexity: **O(N)

As we are constructing a binary search tree of size ‘N’, where ‘N’ is the total number of nodes, therefore, the overall space complexity will be O(N).

You can also read about __insertion into bst__.

## Frequently Asked Questions

### What is the Binary tree?

A binary tree is a type of tree in which a node can have two children, commonly known as the left and right children of the node.

### Number of types of binary tree traversals?

Mainly there are three types of binary tree traversals, which are as follows:-

- Inorder
- Preorder
- Postorder

### What is the inorder binary tree traversal?

In inorder binary tree traversal, the left subtree is traversed before the root node, and the right subtree is traversed after the root node. The order followed by this tree traversal is ‘LDR’ where ‘L’ denotes the left child, ‘D’ denotes the root node, and ‘R’ denotes the right child.

## Conclusion

In this article, we discussed the What is print all odd nodes of binary search tree problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

**Recommended Problems:**

**Recommended Reading:**

Until then, All the best for your future endeavors, and Keep Coding.