TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Find the Smallest Element in a Binary Tree

Program to Find the Smallest Element in a Binary Tree on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to find the smallest element in a Binary Tree.

Explanation

In this program, we will find out the smallest node in the given binary tree. We first define variable min that will hold root's data. Then, we traverse through left sub-tree to find the smallest node in left subtree. Compare it with min and store minimum of two in variable min. Then, we traverse through right subtree to find smallest node and compare it with min. At the end, min will have the smallest node.

Program to find the smallest element in a Binary Tree

Above diagram represents a binary tree. Initially, min will hold 4. Recursive through left subtree.

min = 4, leftMin = 2    =>  (2 < 4) then min = 2
min = 2, leftMin = 1    =>  (1 < 2) then min = 1

Recursive through right subtree.

min = 1, rightMin = 3  =>  (1 < 3) then min = 1
Recurse in left subtree of 5
min = 1, leftMin = 5    =>  (1 < 5) then min = 1

Recurse in right subtree of 3

min = 1, rightMin = 6  =>  (1 < 6) then min = 1

So, smallest node in above binary tree is 1.

Algorithm

  1. Define Node class which has three attributes namely: data, left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represent root node of the tree and initialize it to null.
  1. smallestElement() will find out the smallest node in binary tree:
    1. It checks whether root is null, which means tree is empty.
    2. If tree is not empty, define a variable min that will store temp's data.
    3. Find out the minimum node in left subtree by calling smallestElement() recursively. Store that value in leftMin. Compare the value of min with leftMin and store the minimum of two to min.
    4. Find out the minimum node in right subtree by calling smallestElement() recursively. Store that value in rightMin. Compare the value of min with rightMin and store the maximum of two to min.
    5. At the end, min will hold the smallest node in the binary tree.

Solution

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class SmallestNode:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
    
    #smallestElement() will find out the smallest node in the binary tree
    def smallestElement(self, temp):
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return 0;
        
        else:
            #Variable minimum will store temp's data
            minimum = temp.data;
            
            #It will find smallest element in left subtree
            if(temp.left != None):
                leftMin = self.smallestElement(temp.left);
                #If value of minimum is greater than leftMin then store the value of leftMin into minimum
                minimum = min(minimum, leftMin);
                
            #It will find smallest element in right subtree
            if(temp.right != None):
                rightMin = self.smallestElement(temp.right);
                #If value of minimum is greater than rightMin then store the value of rightMin into minimum
                minimum = min(minimum, rightMin);
            
            return minimum;
 
bt = SmallestNode();
#Add nodes to the binary tree
bt.root = Node(4);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(1);
bt.root.right.left = Node(5);
bt.root.right.right = Node(6);
 
#Display smallest node in the binary tree
print("Smallest element in the binary tree: " + str(bt.smallestElement(bt.root)));

Output:

Smallest element in the binary tree: 1

C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//smallestElement() will find out the smallest node in the binary tree
int smallestElement(struct node *temp){
    //Check whether tree is empty
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else{
        int leftMin, rightMin;
        //Min will store temp's data
        int min = temp->data;
        
        //It will find smallest element in left subtree
        if(temp->left != NULL){
            leftMin = smallestElement(temp->left);
            //If min is greater than leftMin then store the value of leftMin into min
            min = (min > leftMin) ? leftMin : min;
        }
      
        //It will find smallest element in right subtree
        if(temp->right != NULL){
            rightMin = smallestElement(temp->right);
            //If min is greater than rightMin then store the value of rightMin into min
            min = (min > rightMin) ? rightMin : min;
        }
    return min;
    }
}
      
int main()
{
    //Add nodes to the binary tree
    root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(1);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
        
    //Display smallest node in the binary tree
    printf("Smallest element in the binary tree: %d", smallestElement(root));
    return 0;
}

Output:

Smallest element in the binary tree: 1

JAVA

public class SmallestNode {
      //Represent the node of binary tree
      public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
        }
      }
      
      //Represent the root of binary tree
      public Node root;
      
      public SmallestNode(){
          root = null;
      }
      
      //smallestElement() will find out the smallest node in the binary tree
      public int smallestElement(Node temp){
          //Check whether tree is empty
          if(root == null) {
              System.out.println("Tree is empty");
              return 0;
          }
          else {
                int leftMin, rightMin;
                //Min will store temp's data
                int min = temp.data;
                
                //It will find smallest element in left subtree
                if(temp.left != null){
                  leftMin = smallestElement(temp.left);
                  //If min is greater than leftMin then store the value of leftMin into min
                  min = Math.min(min, leftMin);
                }
                
                //It will find smallest element in right subtree
                if(temp.right != null){
                  rightMin = smallestElement(temp.right);
                  //If min is greater than rightMin then store the value of rightMin into min
                  min = Math.min(min, rightMin);
                }
                return min;
          }
      }
      
      public static void main(String[] args) {
        
        SmallestNode bt = new SmallestNode();
        //Add nodes to the binary tree
        bt.root = new Node(4);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(1);
        bt.root.right.left = new Node(5);
        bt.root.right.right = new Node(6);
        
        //Display smallest node in the binary tree
        System.out.println("Smallest element in the binary tree: " + bt.smallestElement(bt.root));
      }
}

Output:

Smallest element in the binary tree: 1

C#

using System; 
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to NULL
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class SmallestNode<T> where T : IComparable<T>{
            //Represent the root of binary tree
            public Node<T> root;
 
            public SmallestNode(){
                root = null;
            }
        
        //smallestElement() will find out the smallest node in the binary tree
        public T smallestElement(Node<T> temp){
            //Check whether tree is empty
            if(root == null) {
                Console.WriteLine("Tree is empty");
                return default(T);
            }
            T leftMin, rightMin;
            //Min will store temp's data
            T min = temp.data;
 
            //It will find smallest element in left subtree
            if(temp.left != null){
                leftMin = smallestElement(temp.left);
                //If min is greater than leftMin then store the value of leftMin into min
                min = (min.CompareTo(leftMin) > 0) ? leftMin : min;
            }
 
            //It will find smallest element in right subtree
            if(temp.right != null){
                rightMin = smallestElement(temp.right);
                //If min is greater than rightMin then store the value of rightMin into min
                min = (min.CompareTo(rightMin) > 0) ? rightMin : min;
            }
            return min;
          }
    }
        
    public static void Main()
    {
        SmallestNode<int> bt = new SmallestNode<int>();
        //Add nodes to the binary tree
        bt.root = new Node<int>(4);
        bt.root.left = new Node<int>(2);
        bt.root.right = new Node<int>(3);
        bt.root.left.left = new Node<int>(1);
        bt.root.right.left = new Node<int>(5);
        bt.root.right.right = new Node<int>(6);
        
        //Display smallest node in the binary tree
        Console.WriteLine("Smallest element in the binary tree: " + bt.smallestElement(bt.root));
        }    
    }
}

Output:

Smallest element in the binary tree: 1

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class SmallestNode{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
     //smallestElement() will find out the smallest node in the binary tree
     function smallestElement($temp){
          //Check whether tree is empty
          if($this->root == NULL) {
              print "Tree is empty<br>";
              return 0;
          }
          else {
                //$min will store $temp's data
                $min = $temp->data;
                
                //It will find smallest element in left subtree
                if($temp->left != NULL){
                    $leftMin = $this->smallestElement($temp->left);
                    //If $min is greater than $leftMin then store the value of $leftMin into $min
                    $min = min($min, $leftMin);
                }
                
                //It will find smallest element in right subtree
                if($temp->right != NULL){
                    $rightMin = $this->smallestElement($temp->right);
                    //If $min is greater than $rightMin then store the value of $rightMin into $min
                    $min = min($min, $rightMin);
                }
                return $min;
          }
      }
}
$bt = new SmallestNode();
//Add nodes to the binary tree
$bt->root = new Node(4);
$bt->root->left = new Node(2);
$bt->root->right = new Node(3);
$bt->root->left->left = new Node(1);
$bt->root->right->left = new Node(5);
$bt->root->right->right = new Node(6);
 
//Display smallest node in the binary tree
print "Smallest element in the binary tree: " . $bt->smallestElement($bt->root);      
?>
</body>
</html>

Output:

Smallest element in the binary tree: 1

Next TopicPrograms List




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf