Print all Nodes of a Binary Tree Less Than N

• Write a c program to print nodes of binary tree smaller than N

Given a binary tree, we have to print all nodes whose value is less than N. We have to traverse each node of binary tree and compare it value with K. We can use any traversal like preOrder, postOrder or inOrder. In this program, we will use InOrder traversal. Below is the structure of binary tree node.

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

---

Algorithm to count all nodes whose value is less than k
Let "root" be the pointer to the root node of binary tree.

• If root is equal to NULL, return.
• Perform inOrder traversal and for every node compare it's value with N. If node's value is less than N then print it otherwise continue.

Time Complexity : O(n)

---

C program to print all nodes of binary tree smaller than N

#include <stdio.h>

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

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            5
           / \
         -2    8
        / \    \
       12 -3    2
      / \
     4  10
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(5);
 
    root->left = getNewNode(-2);
    root->right = getNewNode(8);
 
    root->left->left = getNewNode(12);
    root->left->right = getNewNode(-3);
    root->right->right = getNewNode(2);
 
    root->left->left->left = getNewNode(4);
    root->left->left->right = getNewNode(10);
    
    return root;

}

/*
Does InOrder Traversal and check if current node is less than K. 
*/
void printSmallerNodes(struct node *nodeptr, int k){
    if(nodeptr != NULL){
        /* Recursively print smaller nodes in left sub-tree */
        printSmallerNodes(nodeptr->left, k);
        /* If current node is less than k, then prints it */
        if(nodeptr->data < k)
           printf("%d ", nodeptr->data);
        /* Recursively print smaller nodes in right sub-tree */
        printSmallerNodes(nodeptr->right, k);
    }
}
int main() {
    struct node *root = generateBTree();    
    
    printf("Nodes Less than 7\n");
    printSmallerNodes(root, 7);
    printf("\nNodes Less than 10\n");
    printSmallerNodes(root, 10);
    printf("\nNodes Less than 20\n");
    printSmallerNodes(root, 20);
    
    getchar();
    return 0; 
}

Output

Nodes Less than 7
4 -2 -3 5 2
Nodes Less than 10
4 -2 -3 5 8 2
Nodes Less than 20
4 12 10 -2 -3 5 8 2