Print All Odd Nodes Of Binary Search Tree
Introduction
This blog will discuss the efficient approach to solve the print all the odd nodes of the binary search tree problem. Before jumping into the problem to print all the odd nodes of the binary search tree, let’s first understand what binary search tree is,
A Binary Search Tree is a type of binary tree in which a node can have at most two children, commonly known as the left and right children of the node, and the value of all the nodes in the left subtree must be less than or equal to the value of the root whereas the value of all the nodes in the right subtree must be greater than or equal to the value of the root. Its class has three data members who are as follows:-
- Data
- Left Node pointer
- Right Node pointer
For more information on binary search trees, refer to this link.
Problem statement
In this problem, we need to print all the odd nodes of the binary search tree.
For Example:-
Binary Search Tree:-
Output:-
3 | 5 | 7 | 15 |
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).
Frequently asked questions
Q1) What is the Binary tree?
Ans) 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.
Q2) Number of types of binary tree traversals?
Ans) Mainly there are three types of binary tree traversals, which are as follows:-
- Inorder
- Preorder
- Postorder
Q3) What is the inorder binary tree traversal?
Ans) 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.
Key takeaways
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.
Until then, All the best for your future endeavors, and Keep Coding.
Comments
No comments yet
Be the first to share what you think