CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find the smallest element in a Binary Tree.ExplanationIn 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 subtree 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. 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
SolutionPython#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 JAVApublic 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
