Given a binary search tree. The task is to print all even nodes of the binary search tree.
Examples:
Input :
5
/ \
3 7
/ \ / \
2 4 6 8
Output : 2 4 6 8
Input :
14
/ \
12 17
/ \ / \
8 13 16 19
Output : 8 12 14 16
Approach: Traverse the Binary Search tree and check if current node’s value is even. If yes then print it otherwise skip that node.
Below is the implementation of the above Approach:
C++
// C++ program to print all even node of BST#include <bits/stdc++.h>using namespace std;// create Treestruct Node { int key; struct Node *left, *right;};// A utility function to create a new BST nodeNode* newNode(int item){ Node* temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp;}// A utility function to do inorder traversal of BSTvoid inorder(Node* root){ if (root != NULL) { inorder(root->left); cout << root->key << " "; inorder(root->right); }}/* A utility function to insert a new node with given key in BST */Node* insert(Node* node, int key){ /* If the tree is empty, return a new node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* return the (unchanged) node pointer */ return node;}// Function to print all even nodesvoid evenNode(Node* root){ if (root != NULL) { evenNode(root->left); // if node is even then print it if (root->key % 2 == 0) cout << root->key << " "; evenNode(root->right); }}// Driver Codeint main(){ /* Let us create following BST 5 / \ 3 7 / \ / \ 2 4 6 8 */ Node* root = NULL; root = insert(root, 5); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 7); root = insert(root, 6); root = insert(root, 8); evenNode(root); return 0;} |
Java
// Java program to print all even node of BST class GfG { // create Tree static class Node { int key; Node left, right; }// A utility function to create a new BST node static Node newNode(int item) { Node temp = new Node(); temp.key = item; temp.left = null; temp.right = null; return temp; } // A utility function to do inorder traversal of BST static void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.key + " "); inorder(root.right); } } /* A utility function to insert a new node with given key in BST */static Node insert(Node node, int key) { /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node; } // Function to print all even nodes static void evenNode(Node root) { if (root != null) { evenNode(root.left); // if node is even then print it if (root.key % 2 == 0) System.out.print(root.key + " "); evenNode(root.right); } } // Driver Code public static void main(String[] args) { /* Let us create following BST 5 / \ 3 7 / \ / \ 2 4 6 8 */ Node root = null; root = insert(root, 5); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 7); root = insert(root, 6); root = insert(root, 8); evenNode(root); }} |
Python3
# Python3 program to print all even node of BST # create Tree # to create a new BST node class newNode: # Construct to create a new node def __init__(self, key): self.key = key self.left = None self.right = None# A utility function to do inorder # traversal of BST def inorder(root) : if (root != None): inorder(root.left) printf("%d ", root.key) inorder(root.right) """ A utility function to insert a new node with given key in BST """def insert(node, key): """ If the tree is empty, return a new node """ if (node == None): return newNode(key) """ Otherwise, recur down the tree """ if (key < node.key): node.left = insert(node.left, key) else: node.right = insert(node.right, key) """ return the (unchanged) node pointer """ return node # Function to print all even nodes def evenNode(root) : if (root != None): evenNode(root.left) # if node is even then print it if (root.key % 2 == 0): print(root.key, end = " ") evenNode(root.right) # Driver Code if __name__ == '__main__': """ Let us create following BST 5 / \ 3 7 / \ / \ 2 4 6 8 """ root = None root = insert(root, 5) root = insert(root, 3) root = insert(root, 2) root = insert(root, 4) root = insert(root, 7) root = insert(root, 6) root = insert(root, 8) evenNode(root) # This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to print all even node of BST using System;class GfG { // create Tree class Node { public int key; public Node left, right; } // A utility function to // create a new BST node static Node newNode(int item) { Node temp = new Node(); temp.key = item; temp.left = null; temp.right = null; return temp; } // A utility function to do // inorder traversal of BST static void inorder(Node root) { if (root != null) { inorder(root.left); Console.Write(root.key + " "); inorder(root.right); } } /* A utility function to insert a new node with given key in BST */ static Node insert(Node node, int key) { /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node; } // Function to print all even nodes static void evenNode(Node root) { if (root != null) { evenNode(root.left); // if node is even then print it if (root.key % 2 == 0) Console.Write(root.key + " "); evenNode(root.right); } } // Driver Code public static void Main(String[] args) { /* Let us create following BST 5 / \ 3 7 / \ / \ 2 4 6 8 */ Node root = null; root = insert(root, 5); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 7); root = insert(root, 6); root = insert(root, 8); evenNode(root); } } // This code has been contributed // by PrinciRaj1992 |
Javascript
<script>// JavaScript program to print all even node of BST // create Tree class Node { constructor() { this.key = 0; this.left = null; this.right = null; } } // A utility function to create a new BST node function newNode(item) { var temp = new Node(); temp.key = item; temp.left = null; temp.right = null; return temp; } // A utility function to do inorder traversal of BST function inorder(root) { if (root != null) { inorder(root.left); document.write(root.key + " "); inorder(root.right); } } /* A utility function to insert a new node with given key in BST */function insert(node , key) { /* If the tree is empty, return a new node */ if (node == null) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node; } // Function to print all even nodes function evenNode(root) { if (root != null) { evenNode(root.left); // if node is even then print it if (root.key % 2 == 0) document.write(root.key + " "); evenNode(root.right); } } // Driver Code /* Let us create following BST 5 / \ 3 7 / \ / \ 2 4 6 8 */ var root = null; root = insert(root, 5); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 7); root = insert(root, 6); root = insert(root, 8); evenNode(root); // This code contributed by aashish1995 </script> |
Output
2 4 6 8
Complexity Analysis:
- Time Complexity: O(N)
- Here N is the number of nodes and as we have to visit every node the time complexity is O(N).
- Auxiliary Space: O(h)
- Here h is the height of the tree and extra space is used in recursion call stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
