Print All Odd Nodes Of Binary Search Tree

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;
}

You can also try this code with Online C++ Compiler

Run Code

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:

• Print Nodes At Distance K From Node
• Kth Ancestor Of A Node In Binary Tree
• Segregate Even And Odd Nodes In A Linked List
   

Recommended Reading:

• Difference Between Binary Tree and Binary Search Tree
• Implementing Forward Iterator in BST
• Print All Even Nodes of A Binary Search Tree
• Count Of Smaller Numbers After Self
• Count The Number of Binary Search Trees Present in Binary Tree
• Check if Each Internal Node of BST has Exactly one Child
• Maximum Height of Binary Search Tree Created From the Given Array
   

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