Print all the Even Nodes of a Binary Search Tree

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Binary search tree (BST)

Before jumping to the question, let’s understand what a Binary search tree is:

A Binary search tree (BST)  is a type of binary tree in which the nodes are arranged in a specific order. It is also known as an ordered binary tree.

Properties of a Binary search tree (BST):

• The value of all the nodes in the left subtree of a node is smaller than the node’s value.
• All the nodes in the right subtree of a node are greater than the node’s value.
• All the root node’s left and right subtrees must follow the above properties.

Example:

Problem statement 

We are given a Binary search tree. Our task is to print all the even nodes (nodes with even values) of the given Binary search tree.

Example:

Input1:

Output1: 18 20 50 60

Input2: 

Output2: 10 12 16 18

Approach

The idea is straightforward: traverse all the Binary search tree nodes. We check for every node if the current node’s value is even or not. If the current node’s value is even, we print the node. Else we ignore the node.

For traversing the tree, we can use any traversal technique. Here we are using the inorder traversal (left root right) technique for traversing the Binary search tree because it prints all the even nodes of the Binary search tree from left to right order.
 

Recursive code of inorder traversal:

We can modify the above code of the inorder traversal technique to print only the even nodes of the Binary search tree. So, we add that if the current node’s value is even, then only print the node else, ignore the node, traverse the other nodes, and do the same process.
 

Steps of print_even_nodes() function:

• Recursively call the print_even_nodes() function for the left subtree.
• Print the root->data if the root value is even.
• Recursively call the print_even_nodes() function for the right subtree.
   

Must Read Recursive Binary Search.

Code in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Node* new_node(int x)
{
    Node* freshnode = new Node();
    freshnode->data = x;
    freshnode->left = NULL;
    freshnode->right = NULL;

    return (freshnode);
}
Node* insert_bst( Node* node, int data)
{

    if (node == NULL)
        return (new_node(data));
    else {
        if (data <= node->data)
            node->left = insert_bst(node->left, data);
        else
            node->right = insert_bst(node->right, data);

        return node;
    }
}

void print_even_nodes( Node* root)
{
    if (root == NULL)
        return;
    print_even_nodes(root->left);
    if (root->data % 2 == 0)
        cout << root->data << " ";
    print_even_nodes(root->right);
}

int main()
{
    Node* root = NULL;
    root = insert_bst(root, 50);
    insert_bst(root, 20);
    insert_bst(root, 63);
    insert_bst(root, 18);
    insert_bst(root, 25);
    insert_bst(root, 60);
    insert_bst(root, 81);

    print_even_nodes(root);

    cout << endl;

    return 0;
}

Output

18 20 50 60

Complexity Analysis

Time complexity: O(n), where n is the number of nodes in the given tree, traversing all the nodes in the Binary search tree.

Space complexity: O(n), as the recursion stack at max contains all the nodes of the Binary search tree.

You can also read about insertion into bst.