Second largest element in BST

Second largest element in BST

Here given code implementation process.

//C Program 
//Second largest element in BST
#include <stdio.h>

#include <stdlib.h>
 //structure of Binary Search Tree node
struct Node {
  int data;
  struct Node *left, *right;
};

//Adding a new node in binary search tree
void add(struct Node **root, int data) {
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));

  if (new_node != NULL) {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL; //Initially node right-pointer is NULL

    if ( *root == NULL) {
      //When adds a first node in binary tree
      *root = new_node;
    } else {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while (find != NULL) {
        if (find->data > data) {
          if (find->left == NULL) {
            find->left = new_node;
            break;
          } else { //visit left sub-tree
            find = find->left;
          }
        } else {
          if (find->right == NULL) {
            find->right = new_node;
            break;
          } else {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

//Find the 2nd largest node in binary tree
void find_second_big(struct Node *root, int *counter, struct Node **element) {
  if (root != NULL) {

    find_second_big(root->right, counter, element);
    if ( *counter == 2) {
      return;
    }
    if ( *element == NULL || ( *element)->data > root->data) {
      //Modified counter variable by one
      ( *counter) ++;
      *element = root;

    }


    find_second_big(root->left, counter, element);

  }
}
void second_big(struct Node *root) {
  if (root == NULL) {
    //When BST are no have elements
    printf("Empty Binary Search Tree\n");
  } else {

    int counter = 0;
    struct Node *element = NULL;
    find_second_big(root, & counter, & element);

    if (counter < 2) {
      //If In case 2nd Largest node are 
      //Not exist in binary search tree, then
      printf("Second Largest node are not exist  \n");
    } else {
      printf("Second largest node : %d \n", element->data);
    }
  }


}
int main() {

  struct Node *root = NULL;

  //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   / \
     3   5 8   10
            \    \
             9   10
  */

  add( &root, 7);
  add( &root, 4);
  add( &root, 3);
  add( &root, 5);
  add( &root, 10);
  add( &root, 8);
  add( &root, 10);
  add( &root, 9);
  add( &root, 10);

  second_big(root);


  return 0;
}

Output

Second largest node : 9
/*
  C++ Program
  Second largest element in BST
*/
#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  int counter;
  Node *result;
  BinarySearchTree() {
    this->root = NULL;
    this->result = NULL;
    this->counter = 0;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << ("\nMemory Overflow\n");
    }
  }
  void find_second_big(Node *head) {
    if (head != NULL) {
      this->find_second_big(head->right);
      if (this->counter == 2) {
        return;
      }
      if (this->result == NULL || this->result->data > head->data) {
        this->counter++;
        this->result = head;
      }
      this->find_second_big(head->left);
    }
  }
  void second_big() {
    if (this->root == NULL) {
      cout << ("Empty Binary Search Tree\n");
    } else {
      this->counter = 0;
      this->result = NULL;
      this->find_second_big(this->root);
      if (this->counter < 2) {
        cout << "Second Largest node are not exist  \n";
      } else {
        cout << "Second largest node : " << this->result->data << "\n";
      }
    }
  }
};

int main() {
  BinarySearchTree obj;
  /*
          7
        /   \
       4     10
      / \   / \
     3   5 8   10
            \    \
             9   10
  */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(10);
  obj.add(9);
  obj.add(10);
  obj.second_big();
  return 0;
}

Output

Second largest node : 9
//Java program
//Second largest element in BST

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;

  public int counter;

  public Node result;
  BinarySearchTree()
  {
    root = null;
    result = null;
    counter = 0;
  }
  //insert a node in BST
  public void add(int value)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if(new_node != null)
    {
      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= value)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.print("\nMemory Overflow\n");
    }
  }
  //Find the 2nd largest node in binary tree
  public void  find_second_big(Node head) {
    if (head != null) {

      find_second_big(head.right);
      if (this.counter == 2) {
        return;
      }
      if (result == null || result.data > head.data) {
        //Modified counter variable by one
        this.counter ++;
        result = head;
      }

      find_second_big(head.left);
    }
  }
  public void  second_big() {
    if (root == null) {
      //When BST are no have elements
      System.out.print("Empty Binary Search Tree\n");
    } else {

      this.counter = 0;
      this.result = null;
      find_second_big(root);

      if (this.counter < 2) {
        //If In case 2nd Largest node are 
        //Not exist in binary search tree

        System.out.print("Second Largest node are not exist  \n");
      } else {
        System.out.print("Second largest node : "+ result.data +"\n");
      }
    }
  }
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();

    //Add nodes in binary search tree
    /*
            7
          /   \
         4     10
        / \   / \
       3   5 8   10
              \    \
               9   10
    */

    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(10);
    obj.add(8);
    obj.add(10);
    obj.add(9);
    obj.add(10);

    obj.second_big();

  }
}

Output

Second largest node : 9
//C# program
//Second largest element in BST
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;

	public int counter;

	public Node result;
	BinarySearchTree()
	{
		root = null;
		result = null;
		counter = 0;
	}
	//insert a node in BST
	public void add(int value)
	{
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if(new_node != null)
		{
			if(root == null)
			{
				//When adds a first node in binary tree
				root = new_node;
			}
			else
			{
				Node find = root;

				//add new node to proper position
				while(find != null)
				{
					if(find.data >= value)
					{ 
						if(find.left==null)
						{
							find.left = new_node;
							break;
						}
						else
						{ 
							//visit left sub-tree
							find = find.left;
						}
					}
					else
					{
						if(find.right == null)
						{
							find.right = new_node;
							break;
						}
						else
						{
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		}
		else
		{
			Console.Write("\nMemory Overflow\n");
		}
	}
	//Find the 2nd largest node in binary tree
	public void  find_second_big(Node head) {
		if (head != null) {

			find_second_big(head.right);
			if (this.counter == 2) {
				return;
			}
			if (result == null || result.data > head.data) {
				//Modified counter variable by one
				this.counter ++;
				result = head;
			}

			find_second_big(head.left);
		}
	}
	public void  second_big() {
		if (root == null) {
			//When BST are no have elements
			Console.Write("Empty Binary Search Tree\n");
		} else {

			this.counter = 0;
			this.result = null;
			find_second_big(root);

			if (this.counter < 2) {
				//If In case 2nd Largest node are 
				//Not exist in binary search tree

				Console.Write("Second Largest node are not exist  \n");
			} else {
				Console.Write("Second largest node : "+ result.data +"\n");
			}
		}
	}
	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();

		//Add nodes in binary search tree
		/*
            7
          /   \
         4     10
        / \   / \
       3   5 8   10
              \    \
               9   10
    */

		obj.add(7);
		obj.add(4);
		obj.add(3);
		obj.add(5);
		obj.add(10);
		obj.add(8);
		obj.add(10);
		obj.add(9);
		obj.add(10);

		obj.second_big();

	}
}

Output

Second largest node : 9
# Python Program 
# Second largest element in BST
class Node :
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
    self.result = None
    self.counter = 0
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def find_second_big(self, head) :
    if (head != None) :
      self.find_second_big(head.right)
      if (self.counter == 2) :
        return
      
      if (self.result == None or self.result.data > head.data) :
        self.counter += 1
        self.result = head
      
      self.find_second_big(head.left)
    
  
  def second_big(self) :
    if (self.root == None) :
      print("Empty Binary Search Tree\n")
    else :
      self.counter = 0
      self.result = None
      self.find_second_big(self.root)
      if (self.counter < 2) :
        print("Second Largest node are not exist  \n")
      else :
        print("Second largest node : ", self.result.data ,"\n")
      
    
  
def main() :
  obj = BinarySearchTree()
  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(10)
  obj.add(8)
  obj.add(10)
  obj.add(9)
  obj.add(10)
  obj.second_big()
  

if __name__ == "__main__":
  main()

Output

Second largest node : 9
# Ruby Program
# Second largest element in BST
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root, :counter, :result
	attr_accessor :root, :counter, :result
	def initialize() 
		@root = nil
		@result = nil
		@counter = 0
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def find_second_big(head) 
		if (head != nil) 
			self.find_second_big(head.right)
			if (self.counter == 2) 
				return
			end
			if (@result == nil or @result.data > head.data) 
				self.counter += 1
				@result = head
			end
			self.find_second_big(head.left)
		end
	end
	def second_big() 
		if (@root == nil) 
			print("Empty Binary Search Tree\n")
		else 
			self.counter = 0
			self.result = nil
			self.find_second_big(@root)
			if (self.counter < 2) 
				print("Second Largest node are not exist  \n")
			else 
				print("Second largest node  : ", @result.data ,"\n")
			end
		end
	end
end
def main() 
	obj = BinarySearchTree.new()
	obj.add(7)
	obj.add(4)
	obj.add(3)
	obj.add(5)
	obj.add(10)
	obj.add(8)
	obj.add(10)
	obj.add(9)
	obj.add(10)
	obj.second_big()
end


main()

Output

Second largest node : 9
<?php
/*
  Php Program
  Second largest element in BST
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;
  public $counter;
  public $result;

  function __construct() {
    $this->root = null;
    $this->result = null;
    $this->counter = 0;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function find_second_big($head) {
    if ($head != null) {
      $this->find_second_big($head->right);
      if ($this->counter == 2) {
        return;
      }
      if ($this->result == null || $this->result->data > $head->data) {
        $this->counter++;
        $this->result = $head;
      }
      $this->find_second_big($head->left);
    }
  }
  public  function second_big() {
    if ($this->root == null) {
      echo("Empty Binary Search Tree\n");
    } else {
      $this->counter = 0;
      $this->result = null;
      $this->find_second_big($this->root);
      if ($this->counter < 2) {
        echo("Second Largest node are not exist  \n");
      } else {
        echo("Second largest node : ". $this->result->data ."\n");
      }
    }
  }
}
function main() {
  $obj = new BinarySearchTree();
  /*
          7
        /   \
       4     10
      / \   / \
     3   5 8   10
            \    \
             9   10
  */
  $obj->add(7);
  $obj->add(4);
  $obj->add(3);
  $obj->add(5);
  $obj->add(10);
  $obj->add(8);
  $obj->add(10);
  $obj->add(9);
  $obj->add(10);
  $obj->second_big();
}
main();

Output

Second largest node : 9
/*
  Node JS Program
  Second largest element in BST
*/
class Node {
	
	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {

	constructor() {
		this.root = null;
		this.result = null;
		this.counter = 0;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	find_second_big(head) {
		if (head != null) {
			this.find_second_big(head.right);
			if (this.counter == 2) {
				return;
			}
			if (this.result == null || this.result.data > head.data) {
				this.counter++;
				this.result = head;
			}
			this.find_second_big(head.left);
		}
	}
	second_big() {
		if (this.root == null) {
			process.stdout.write("Empty Binary Search Tree\n");
		} else {
			this.counter = 0;
			this.result = null;
			this.find_second_big(this.root);
			if (this.counter < 2) {
				process.stdout.write("Second Largest node are not exist  \n");
			} else {
				process.stdout.write("Second largest node : " + this.result.data + "\n");
			}
		}
	}
}
function main() {
	var obj = new BinarySearchTree();
	/*
          7
        /   \
       4     10
      / \   / \
     3   5 8   10
            \    \
             9   10
    */
	obj.add(7);
	obj.add(4);
	obj.add(3);
	obj.add(5);
	obj.add(10);
	obj.add(8);
	obj.add(10);
	obj.add(9);
	obj.add(10);
	obj.second_big();
}
main();

Output

Second largest node : 9
/*
  Swift 4 Program
  Second largest element in BST
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  var counter: Int;
  var result: Node? ;
  init() {
    self.root = nil;
    self.result = nil;
    self.counter = 0;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func find_second_big(_ head: Node? ) {
    if (head != nil) {
      self.find_second_big(head!.right);
      if (self.counter == 2) {
        return;
      }
      if (self.result == nil || self.result!.data > head!.data) {
        self.counter += 1;
        self.result = head;
      }
      self.find_second_big(head!.left);
    }
  }
  func second_big() {
    if (self.root == nil) {
      print("Empty Binary Search Tree\n");
    } else {
      self.counter = 0;
      self.result = nil;
      self.find_second_big(self.root);
      if (self.counter < 2) {
        print("Second Largest node are not exist  \n");
      } else {
        print("Second largest node : ", self.result!.data ,"\n");
      }
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
          7
        /   \
       4     10
      / \   / \
     3   5 8   10
            \    \
             9   10
  */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(10);
  obj.add(9);
  obj.add(10);
  obj.second_big();
}
main();

Output

Second largest node : 9


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved