Sunday, June 5, 2022

Method Overriding in Python

Method overriding is an OOPS concept which provides ability to change the implementation of a method in a child class which is already defined in one of its super class. If there is a method in a super class and method having the same name and same number of arguments in a child class then the child class method is said to be overriding the parent class method.

Method overriding helps in hierarchical ordering where we move from general implementation in the super class to more specific implementation in the child classes.


Method overriding Python example

In the example there is a class Person with fields name and age and a child class Employee with an additional field empId. There is a method displayData in the Person class to display value of the fields. In the Employee class that method is overridden to display empId too.

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def displayData(self):
    print('In parent class displayData method')
    print(self.name)
    print(self.age)

class Employee(Person):
  def __init__(self, name, age, id):
    # calling constructor of super class
    super().__init__(name, age)
    self.empId = id

  def displayData(self):
    print('In child class displayData method')
    print(self.name)
    print(self.age)
    print(self.empId)

#Person class object
person = Person('John', 40)
person.displayData()
#Employee class object
emp = Employee('John', 40, 'E005')
emp.displayData()

Output

In parent class displayData method
John
40
In child class displayData method
John
40
E005

In the example when the displayData() method is called with Person class object, displayData() of the Person class is executed. When displayData() method is called with Employee class object, displayData() of the Employee class is executed. So the appropriate overridden method is called based on the object type, which is an example of Polymorphism.

Calling parent class overridden method from the child class

In the above example in the displayData() method of the child class same fields are printed again causing redundancy. It would be better to call the parent class displayData() method for printing name and age and print empId in the displayData() method of the child class.

To call the overridden method of the super class you can use of the following ways-

  1. Using ClassName.method(self)
  2. Using super()

Calling super class method using class name

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def displayData(self):
    print('In parent class displayData method')
    print(self.name)
    print(self.age)

class Employee(Person):
  def __init__(self, name, age, id):
    # calling constructor of super class
    super().__init__(name, age)
    self.empId = id

  def displayData(self):
    print('In child class displayData method')
    Person.displayData(self)
    print(self.empId)

#Employee class object
emp = Employee('John', 40, 'E005')
emp.displayData()

Output

In child class displayData method
In parent class displayData method
John
40
E005

Calling super class method using super()

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def displayData(self):
    print('In parent class displayData method')
    print(self.name)
    print(self.age)

class Employee(Person):
  def __init__(self, name, age, id):
    # calling constructor of super class
    super().__init__(name, age)
    self.empId = id

  def displayData(self):
    print('In child class displayData method')
    #calling super class method
    super().displayData()
    print(self.empId)

#Employee class object
emp = Employee('John', 40, 'E005')
emp.displayData()

Output

In child class displayData method
In parent class displayData method
John
40
E005

That's all for this topic Method Overriding in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Inheritance in Python
  2. Method Overloading in Python
  3. Name Mangling in Python
  4. Interface in Python
  5. Python break Statement With Examples

You may also like-

  1. Constructor in Python - __init__() function
  2. Python count() method - Counting Substrings
  3. Method Overriding in Java
  4. Difference Between Abstract Class And Interface in Java
  5. How HashSet Works Internally in Java
  6. Installing Hadoop on a Single Node Cluster in Pseudo-Distributed Mode
  7. Sending Email Using Spring Framework Example
  8. Dependency Injection in Spring Framework

Saturday, June 4, 2022

self in Python

In this post we’ll try to understand what is self in Python along with usage examples.

self variable

When you create a new instance of the class, for example-

obj = MyClass() 

a new object is created with its own memory and reference to that object is assigned to the variable obj.

self in Python is also a reference to the current object and it is similar to this in Java and C++. By using self you can access the attributes and methods of a class in python.

Following Python example clarifies how self refers to the current object.

class Person:
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def display_data(self):
    print(self.name)
    print(self.age)

person1 = Person('John', 40)
person1.display_data()
person2 = Person('Jessica', 32)
person2.display_data()

Output

John
40
Jessica
32

As you can see from the output when displayData() method is called on the object person1 it displays the data person1 object is initialized with i.e. self is referring to the person1 object. When displayData() method is called on the object person2 it displays the data person2 object is initialized with i.e. self is referring to the person2 object.

Even in the __init__() function first argument is 'self'. When the constructor is called for initializing the object after it's creation object reference is passed to the first argument (self) of the constructor.

self is not a keyword in Python

All the methods in a class including __init__() must use self as the first parameter but naming this parameter "self" is more of a convention. In Python, self is not a reserved keyword, you can actually use any name as the first parameter of a method though that is not advisable.

Conventionally this parameter is called self in Python and that makes the code more readable.

Why self is not passed in method call

You would have observed in the above example that method call doesn’t include self as a parameter even though method definition does include self as parameter.

Method definition has self as parameter-

def display_data(self):

but when the method is called it is not passed-

person1.display_data()

To understand why method call still works you need to know a little bit about functions and methods in Python.

When you write any def statement with in a class it is a function definition which can be accessed using class name.

A method is a function that belongs to an object.

For example on printing the type of the following statements-

# method call using class name
print(type(Person.display_data))
# method call using object
print(type(person1.display_data))

Output is-

<class 'function'>
<class 'method'>

Coming back to the question how method is called with out an argument. In Python when you call a method using an object, that instance object is passed as the first argument of the function. So a method call person1.display_data() internally becomes Person.display_data(person1) and that person1 reference is assigned to self.

That's all for this topic self in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Class And Object in Python
  2. Name Mangling in Python
  3. Namespace And Variable Scope in Python
  4. Global Keyword in Python With Examples
  5. Python String join() Method

You may also like-

  1. Operator Overloading in Python
  2. Multiple Inheritance in Python
  3. Python Generator, Generator Expression, Yield Statement
  4. Ternary Operator in Python
  5. Java Collections Interview Questions And Answers
  6. Why no Multiple Inheritance in Java
  7. Check if Given String or Number is a Palindrome Java Program
  8. Spring Web MVC Tutorial

Magic Methods in Python With Examples

In Python there are predefined special methods that follow the convention of having method names suffixed and prefixed with double underscores for example __init__(). These special methods are also known as magic methods in Python and also as Dunders (Double UNDERscores).


Python magic methods

These built in methods in Python are known as magic methods as these methods are called automatically to execute the functionality as required by the performed action.

For example when you create an object of a class magic methods __new__() and __init__() are called internally;

  • __new__() is called to create a new instance of class.
  • __init__() is called to initialize the created object.

Another example of magic method is when you add two numbers i.e. a + b, internally __add__() method is called to execute that functionality. More specifically when you write a + b magic method is called internally as a.__add__(b).

Usage of magic methods in Python

Magic methods can be overridden in your class to change the default functionality and fashion these methods as per your custom object needs.

Using magic methods you can do operator overloading in Python. By overriding the corresponding magic method a class can define its own behavior with respect to language operators. For example magic method for multiplication operator (*) is __mul__() so you can overload * operator by overriding __mul__() method in your class.

Available magic methods in Python

There are many magic methods in Python which are called automatically when object is initialized, when object is destroyed, for binary operators, for unary operators, for compound assignment operators, for representing object as string and many mores. We’ll see some of the most used magic methods in this section along with examples of those magic methods.

Magic methods for basic object customization

Magic Method Description
__new__(cls[, ... ])Called to create a new instance of class cls.
__init__(self [, ... ])Called to initialize the object after it is created. This method is called after the instance has been created (by __new__()), but before it is returned to the caller.
__del__(self )Called when the instance is about to be destroyed.

__init__() and __new__() method Python example

In reality most probably __init__() will be the most used magic method for you where as you will explicitly use __new__() method very rarely.

class Person:
  def __new__(cls, x, y):
    print('__new__ called to create object')
    # return created instance
    return super().__new__(cls)
  def __init__(self, name, salary):
    print('__init__ called for object initialization')
    self.name = name
    self.salary = salary

obj1 = Person('John', 4500)
obj2 = Person('Natasha', 6000)

Output

__new__ called to create object
__init__ called for object initialization
__new__ called to create object
__init__ called for object initialization

Magic methods for string representation of an object

Magic Method Description
__repr__(self )Called by the repr() built-in function to compute the “official” string representation of an object.
__str__(self )Called by str(object) and the built-in functions format() and print() to compute the “informal” or nicely printable string representation of an object.
__bytes__(self )Called by bytes to compute a byte-string representation of an object. This should return a bytes object.
__format__(self, format_spec)Called by the format() built-in function, and by extension, evaluation of formatted string literals and the str.format() method, to produce a “formatted” string representation of an object.

__str__() magic method Python example

class Person:
  def __init__(self, name, salary):
    print('__init__ called for object initialization')
    self.name = name
    self.salary = salary
  def __str__(self):
    return "Name - " + self.name + " Salary - " + str(self.salary)

obj1 = Person('John', 4500)
obj2 = Person('Natasha', 6000)
print(obj1)
print(obj2)

Output

__init__ called for object initialization
__init__ called for object initialization
Name - John Salary - 4500
Name - Natasha Salary – 6000

Magic methods for arithmetic operators

Operator Magic Method Description
+__add__(self, other)Additive operator
-__sub__(self, other)Subtraction operator
*__mul__(self, other)Multiplication operator
/__truediv__(self, other)Division with fractional result
%__mod__(self, other)Remainder operator
//__floordiv__(self, other)Division with integer result, discarding any fractional part
**__pow__(self, other)Return a to the power b, for a and b numbers.
@__matmul__(self, other)Matrix Multiplication. Available from version 3.5

Overloading ‘*’ operator in Python

class Point:
  def __init__(self, x):
    self.x = x
  #overriding magic method
  def __mul__(self, other):
    return self.x * other.x

p1 = Point(12)
p2 = Point(5)
print(p1*p2)

Output

60

Magic methods for Comparison operators

Operator Magic Method Description
<__lt__(self, other)less than
<=__le__(self, other)less than or equal to
==__eq__(self, other)equal to
!=__ne__(self, other)not equal to
>__gt__(self, other)greater than
>=__ge___(self, other)greater than or equal to

Magic methods for compound assignment operators

Operator Magic Method Description
+=__iadd__(self, other)Addition assignment
–=__isub__(self, other)Subtraction assignment
*=__imul__(self, other)Multiplication assignment
/=__itruediv__(self, other)Division assignment
%=__imod__(self, other)Modulus assignment
//=__ifloordiv__(self, other)Division with integer result, discarding any fractional part
**=__ipow__(self, other)Return a to the power b, for a and b numbers.
@=__imatmul__(self, other)Matrix Multiplication. Available from version 3.5

Magic methods for unary operators

Operator Magic Method Description
+__pos__(self, other)Unary plus operator; indicates positive value
-__neg__(self, other)Unary minus operator; negates an expression
~__invert__(self, other)Returns the bitwise inverse of the number

Overloading comparison operator (>) in Python

class Person:
  def __init__(self, name, salary):
    self.name = name
    self.salary = salary
  #overriding magic method
  def __gt__(self, other):
    return self.salary > other.salary

obj1 = Person('John', 4500)
obj2 = Person('Natasha', 6000)
print(obj1.name, 'earns more than', obj2.name, '-', obj1 > obj2)

Output

John earns more than Natasha - False

Magic methods for container types

If you want your object to emulate container types (List, tuples) then you can override one of the following magic methods for container types.

Magic Method Description
__len__(self )Called to implement the built-in function len() which returns the length of the container.
__getitem__(self, key)To implement behavior for accessing an item using self[key] notation.
__setitem__(self, key, value)To implement behavior to set an item value using self[key]=value notation.
__delitem__(self, key)To implement behavior to delete an item using del self[key] notation.
__iter__(self )This method is called when an iterator is required for a container.
__reversed__(self )To implement reverse iteration.
__contains__(self, item)To implement membership test operators. Should return true if item is in self, false otherwise.

Overloading len magic method in Python

In the following example class overrides __len__() magic method to return the number of transactions using Account object.

class Account:
  def __init__(self, name, acct_num):
    self.name = name
    self.acct_num = acct_num
    #list to add transactions
    self.transactions = []

  def withdraw(self, amount):
    print('Withdrawing amount for ', self.acct_num)
    self.transactions.append(amount)

  def deposit(self, amount):
    print('Depositing amount for ', self.acct_num)
    self.transactions.append(amount)
        
  #oveririding len magic method
  def __len__(self):
    return len(self.transactions)

pa = Account('Ian', 1001)
pa.withdraw(100)
pa.deposit(500)
pa.withdraw(50)
# Using len method with custom object
print('Total Number of Transactions in account- ', len(pa))

Output

Withdrawing amount for  1001
Depositing amount for  1001
Withdrawing amount for  1001
Total Number of Transactions in account-  3

That's all for this topic Magic Methods in Python With Examples. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Tutorial Page


Related Topics

  1. Passing Object of The Class as Parameter in Python
  2. Abstract Class in Python
  3. Global Keyword in Python With Examples
  4. Multiple Inheritance in Python
  5. Namespace And Variable Scope in Python

You may also like-

  1. Python String split() Method
  2. Python assert Statement
  3. Variable Length Arguments (*args), Keyword Varargs (**kwargs) in Python
  4. Convert String to int in Python
  5. LinkedHashMap in Java With Examples
  6. Object Creation Using new Operator in Java
  7. Benefits, Disadvantages And Limitations of Autowiring in Spring
  8. Data Locality in Hadoop

Friday, June 3, 2022

First Java Program - Hello World Java Program

In this Java tutorial we’ll see how to write your first Java program- A Hello World Java program. A “Hello World” program is just a simple program to display “Hello World” on the screen. Since focus is more on how to write, compile and execute a Java program so better to start with a simple Hello World program.

Writing your first Java program

To write a Java program you can use an IDE like Eclipse which provides an integrated environment to write, compile and execute Java program.

You can also use an editor like notepad to write your first Java program, that will give you a better idea about how to compile and execute a Java program.

In this post we’ll cover both ways of writing Java program-

  • Using text editor like notepad or gedit
  • Using Eclipse IDE
  • Compile and run first Java program -Hello World using text editor

    Open a text editor and write Hello World Java program as given here-

    public class HelloWorld {
      public static void main(String[] args){
        System.out.println("First Java program - Hello world");
      }
    }
    

    Following the convention of file name same as class name in Java save this program file as “HelloWorld.java”.

    From command line go to the location where you have saved your code file and compile it using javac command.

    F:\NETJS>javac HelloWorld.java 
    

    If program compiles successfully you should see a class file HelloWorld.class generated at the same location.

    hello world Java

    Once the code is compiled and the class file is generated you can execute your HelloWorld Java program using the following command to see the message displayed on the screen.

    F:\NETJS>java HelloWorld
    
    First Java program - Hello world // Output
    

    Understanding Java Program

    Now when writing Hello World Java program is done let’s try to understand it.

    1- First thing is to define a class, since Java is an object oriented language so code has to be written with in a class.

    In our program class name is HelloWorld with access modifier as public.

    public class HelloWorld {
     ...
    }
    

    2- In HelloWorld class there is only one method main() which is defined as follows.

      public static void main(String[] args){
        System.out.println("First Java program - Hello world");
      }
    

    Note that in Java, every application must contain a main method. This main method is the starting point of the program execution. The signature of the main method should follow the same convention of being public static void. To get more idea about why main method is public void static refer this post - Why main Method static in Java

    3- Statement with in the main method–

    System.out.println("First Java program - Hello world");
    

    prints the String between the double quotes to the output console.

    Hello World Java program using Eclipse IDE

    For writing your first Java program using Eclipse IDE, first step is to download Eclipse if you don’t have it already.

    Download the version of Eclipse depending on your OS and Java version from here- https://www.eclipse.org/downloads/

    Once Eclipse is downloaded and installed, open it and set the location for the workspace (folder where your projects will be stored).

    1- First thing is to create a new Java project in Eclipse for that-

    1. Choose File – New – Project
    2. Select Java Project from the list and click Next.
      Java program Eclipse
    3. In “Create a Java Project” window, enter a name for your Java project.
    4. Click Finish.
    5. Click Open Perspective for the message “This kind of project is associated with the Java perspective. Do you want to open this perspective now”.

    2- Expand the created project and right click “src” folder. Select New – Class.

    First Java program

    3- In the New Java class window enter the class name “HelloWorld”. Select public static void main(String[] args) checkbox in the “Which method stubs would you like to create?” section.

    4- Click Finish.

    5- In the Java editor opened for this class you should see a HelloWorld class with main method.

    public class HelloWorld {
      public static void main(String[] args) {
        // TODO Auto-generated method stub
      }
    }
    

    6- Add the following code inside main method.

    System.out.println("First Java program - Hello world");
    

    To have a class like this-

    public class HelloWorld {
     public static void main(String[] args) {
      System.out.println("First Java program - Hello world");
     }
    }
    

    7- Save the class. Right click on the program file HelloWorld.java and select Run As – Java Application.

    8- In the console you can see the output.

    Hello World Java program in another method

    Till now we have written the code for printing “Hello World” with in the main method, that is fine for a small program like this but very soon you’ll find out that it’s better to divide code in different methods with in a class. This example gives an idea how to do that.

    public class HelloWorld {
     public static void main(String[] args) {
      HelloWorld obj = new HelloWorld();
      obj.displayMessage();
     }
     
     private void displayMessage() {
      System.out.println("First Java program - Hello world");
     }
    }
    

    Output

    First Java program - Hello world
    

    As you can see in this Hello world example there is a new method displayMessage() that does the work of displaying the message. To call that method class object is created using new operator and using that object the method is called.

    It is getting very repetitive to display the same message again and again, why don’t we write a method to which you can pass the message that is to be displayed.

    public class HelloWorld {
     public static void main(String[] args) {
      HelloWorld obj = new HelloWorld();
      obj.displayMessage("Hello from main");
      obj.displayMessage("Call method again");
     }
     
     private void displayMessage(String msg) {
      System.out.println(msg);
     }
    }
    

    Output

    Hello from main
    Call method again
    

    As you can see now the method has a String argument. By passing value for that argument while calling the method you can display different messages in each call.

    That's all for this topic First Java Program - Hello World Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

    >>>Return to Java Basics Tutorial Page


    Related Topics

    1. Java Pass by Value or Pass by Reference
    2. Primitive Data Types in Java
    3. Java for Loop With Examples
    4. Arithmetic And Unary Operators in Java
    5. String in Java Tutorial

    You may also like-

    1. final Vs finally Vs finalize in Java
    2. Why no Multiple Inheritance in Java
    3. HashSet in Java With Examples
    4. Thread States (Thread Life Cycle) in Java Multi-Threading
    5. Linked List Implementation Java Program
    6. How to Reverse a String in Java
    7. Autowiring in Spring Using XML Configuration
    8. Constructor in Python - __init__() function

    Binary Tree Traversal Using Depth First Search Java Program

    In this post we’ll see a Java program to do a Binary tree traversal using depth first search.

    Binary tree traversal

    For traversing a binary tree you can use one of the following-

    1. Breadth first search
    2. Depth first search

    In the post Binary Tree Traversal Using Breadth First Search Java Program we have already seen Java implementation for binary tree traversal using breadth first search. Now we’ll see Java implementation for the binary tree traversal using depth first search.

    Depth first search

    Contrary to the breadth first search where nodes with in the same level are visited first in depth first search traversal is done by moving to next level of nodes. Control moves to the deepest node and then come back to the parent node when dead end is reached.

    There are several orderings for depth first search of a binary tree- inorder, preorder and postorder which are easy to implement using recursion. Apart from that you can also write a depth first search program using a stack in non-recursive way. So, in this post we’ll see Recursive Java implementation of inorder, preorder and postorder traversal of binary tree as well as iterative (non-recursive) Java implementation.

    Binary tree Inorder traversal Java program

    Logic for Inorder traversal of binary search tree is as follows-

    • Recursively traverse the left subtree.
    • Visit the root node
    • Recursively traverse the right subtree

    Note that inorder traversal of the binary search tree visit the nodes in ascending order so inorder traversal is also used for tree sort.

    // For traversing in order
    public void inOrder(Node node){
      if(node != null){
        inOrder(node.left);
        node.displayData();
        inOrder(node.right);
      }
    }
    

    Binary tree Preoder traversal Java program

    Logic for preorder traversal of binary search tree is as follows-

    • Visit the root node
    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree
    // Preorder traversal
    public void preOrder(Node node){
      if(node != null){
        node.displayData();
        preOrder(node.left);        
        preOrder(node.right);
      }
    }
    

    Binary tree Postoder traversal Java program

    Logic for postorder traversal of binary search tree is as follows-

    • Recursively traverse the left subtree.
    • Recursively traverse the right subtree
    • Visit the root node
    // Postorder traversal
    public void postOrder(Node node){
      if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        node.displayData();       
      }
    }
    

    Depth first search recursive Java program

    Here is a complete Java program for traversing a binary tree using depth first search. In the program there are recursive methods for inorder traversal, preorder traversal and postorder traversal.

    public class DFS {
      // first node
      private Node root;
      DFS(){
        root = null;
      }
      // Class representing tree nodes
      static class Node{
        int value;
        Node left;
        Node right;
        Node(int value){
          this.value = value;
          left = null;
          right = null;        
        }
        public void displayData(){
          System.out.print(value + " ");
        }
      }
      public void insert(int i){
        root = insert(root, i);
      }
        
      //Inserting node - recursive method
      public Node insert(Node node, int value){
        if(node == null){
          return new Node(value);
        }
        // Move to the left if passed value is 
        // less than the current node
        if(value < node.value){
          node.left = insert(node.left, value);
        }
        // Move to the right if passed value is 
        // greater than the current node
        else if(value > node.value){
          node.right = insert(node.right, value);
        }
        return node;
      }
      // For traversing in order
      public void inOrder(Node node){
        if(node != null){
          inOrder(node.left);
          node.displayData();
          inOrder(node.right);
        }
      }
      // Preorder traversal
      public void preOrder(Node node){
        if(node != null){
          node.displayData();
          preOrder(node.left);           
          preOrder(node.right);
        }
      }
      // Postorder traversal
      public void postOrder(Node node){
        if(node != null){
          postOrder(node.left);
          postOrder(node.right);
          node.displayData();          
        }
      }
            
      public static void main(String[] args) {
        DFS bst = new DFS();
        bst.insert(50);
        bst.insert(70);    
        bst.insert(30);
        bst.insert(15);
        bst.insert(35);
        bst.insert(7);
        bst.insert(22);
        bst.insert(31);
        bst.insert(62);
        bst.insert(87);
        System.out.println("Binary tree inorder traversal- ");
        bst.inOrder(bst.root);
        System.out.println("");
        System.out.println("Binary tree postorder traversal- ");
        bst.postOrder(bst.root);
        System.out.println("");
        System.out.println("Binary tree preorder traversal- ");
        bst.preOrder(bst.root);
      }
    }
    

    Output

    Binary tree inorder traversal- 
    7 15 22 30 31 35 50 62 70 87 
    Binary tree postorder traversal- 
    7 22 15 31 35 30 62 87 70 50 
    Binary tree preorder traversal- 
    50 30 15 7 22 35 31 70 62 87 
    

    Depth first search Non-Recursive Java program

    To write a Java program for depth first search of a binary tree using a non-recursive method a stack is used as stack is a Last In First Out (LIFO) data structure. Iterative Java implementation for inorder and preorder traversal is easy to understand.

    Iterative Java implementation for post order traversal of binary tree is a bit complex, as you can see in recursive method the statement to display is after the recursive calls in post order traversal which makes iterative implementation a bit complex.

    Here post order traversal iterative implementation is done using two stacks. In the first stack you add root, left, right and then add root first in the second stack and then the add order would be right and left in the second stack when popped from the first stack. Now popping from second stack would give you the post order of left, right, root.

    Here is a complete Java program for traversing a binary tree using depth first search. In the program there are iterative methods for inorder traversal, preorder traversal and postorder traversal where stack is used as an auxiliary data structure.

    public class DFS {
      // first node
      private Node root;
      DFS(){
        root = null;
      }
      // Class representing tree nodes
      static class Node{
        int value;
        Node left;
        Node right;
        Node(int value){
          this.value = value;
          left = null;
          right = null;        
        }
        public void displayData(){
          System.out.print(value + " ");
        }
      }
      public void insert(int i){
        root = insert(root, i);
      }
        
      //Inserting node - recursive method
      public Node insert(Node node, int value){
        if(node == null){
          return new Node(value);
        }
        // Move to the left if passed value is 
        // less than the current node
        if(value < node.value){
          node.left = insert(node.left, value);
        }
        // Move to the right if passed value is 
        // greater than the current node
        else if(value > node.value){
          node.right = insert(node.right, value);
        }
        return node;
      }
      // For traversing in order
      public void inOrder(){
        if(root == null){
          return;
        }
        Stack<Node> stack = new Stack<>();
        Node current = root;
        while(current != null || !stack.isEmpty()){
          // traverse left subtree
          while(current != null){
            stack.push(current);
            current = current.left;                        
          }
          current = stack.pop();
          current.displayData();
          current = current.right;
        }
        
      }
      // Preorder traversal
      public void preOrder(){
        if(root == null){
          return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
          Node node = stack.pop();
          node.displayData();
          if(node.right != null){
            stack.push(node.right);
          }
          if(node.left != null){
            stack.push(node.left);
          }
        }    
      }
      // Postorder traversal
      public void postOrder(){
        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()) {
          // insert tree root into second stack so that it is last to be popped
          Node node = s1.pop();
          s2.push(node);
          // now follow the post order of pushing the left and right child 
          if(node.left!=null){
            s1.push(node.left);
          }
          if(node.right!=null){
            s1.push(node.right);
          }
        }
        while(!s2.isEmpty()){
          s2.pop().displayData();
        }
      }
            
      public static void main(String[] args) {
        DFS bst = new DFS();
        bst.insert(50);
        bst.insert(70);    
        bst.insert(30);
        bst.insert(15);
        bst.insert(35);
        bst.insert(7);
        bst.insert(22);
        bst.insert(31);
        bst.insert(62);
        bst.insert(87);
        System.out.println("Binary tree inorder traversal- ");
        bst.inOrder();
        System.out.println("");
        System.out.println("Binary tree postorder traversal- ");
        bst.postOrder();
        System.out.println("");
        System.out.println("Binary tree preorder traversal- ");
        bst.preOrder();
      }
    }
    

    Output

    Binary tree inorder traversal- 
    7 15 22 30 31 35 50 62 70 87 
    Binary tree postorder traversal- 
    7 22 15 31 35 30 62 87 70 50 
    Binary tree preorder traversal- 
    50 30 15 7 22 35 31 70 62 87 
    

    That's all for this topic Binary Tree Traversal Using Depth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

    >>>Return to Java Programs Page


    Related Topics

    1. Java Program to Delete a Node From Binary Search Tree (BST)
    2. Deque Implementation in Java Using Doubly Linked List
    3. Heap Sort Program in Java
    4. Find Largest and Second Largest Number in Given Array - Java Program
    5. How to Run a Shell Script From Java Program

    You may also like-

    1. Difference Between Two Dates in Java
    2. Convert String to float in Java
    3. How to Read File From The Last Line in Java
    4. Converting float to int in Java
    5. Adding Tomcat Server to Eclipse
    6. Invoke Method at Runtime Using Java Reflection API
    7. Try-With-Resources in Java With Examples
    8. Spring MessageSource Internationalization (i18n) Support

    Thursday, June 2, 2022

    Binary Tree Traversal Using Breadth First Search Java Program

    In this post we’ll see a Java program to do a Binary tree traversal using breadth first search which is also known as level order traversal of binary tree.

    Breadth first search

    Contrary to the depth first search where traversal is done by moving to node in the next level, in breadth first search all the nodes with in the same level are visited then only next level is visited.

    For depth search Java program refer this post- Binary Tree Traversal Using Depth First Search Java Program

    The level order traversal of the binary tree in the above image will happen in the following order-

    1. Level 0 – 50
    2. Level 1- 30, 70
    3. Level 2- 15, 35, 62, 87
    4. Level 3- 7, 22, 31

    Binary Tree- Breadth first search Java program

    Breadth first Java program for a binary tree can be written using both-

    Breadth first search Recursive Java program

    To write a Java program to recursively do a level order traversal of a binary tree you need to calculate height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.

    public void levelOrder(){
      int height = calculateTreeHeight(root);
      for(int i = 0; i < height; i++){
        levelOrderTraversal(root, i);
      }
    }
    
    // Method for breadth first search
    public void levelOrderTraversal(Node node, int level){
      if(node == null){
        return;
      }
      if(level == 0){
        System.out.print(node.value + " ");
      }else{
        levelOrderTraversal(node.left, level-1);
        levelOrderTraversal(node.right, level-1);
      }    
    }
    

    Breadth first search Non-Recursive Java program

    To write a Java program for level order traversal of a binary tree using a non-recursive method a queue is used. Initially root of the tree is inserted to the queue then you need to do the following until queue is empty.

    1. Poll a node from queue and display its value.
    2. Check if node has left child, if yes add that to the queue.
    3. Check if node has right child, if yes add that to the queue.

    Full Java program for breadth first search or level order traversal of binary tree.

    import java.util.LinkedList;
    import java.util.Queue;
    
    public class BFS {
      // first node
      private Node root;
      BFS(){
        root = null;
      }
      // Class representing tree nodes
      static class Node{
        int value;
        Node left;
        Node right;
        Node(int value){
          this.value = value;
          left = null;
          right = null;        
        }
        public void displayData(){
          System.out.print(value + " ");
        }
      }
      public void insert(int i){
        root = insert(root, i);
      }
        
      //Inserting node - recursive method
      public Node insert(Node node, int value){
        if(node == null){
          return new Node(value);
        }
        // Move to the left if passed value is 
        // less than the current node
        if(value < node.value){
          node.left = insert(node.left, value);
        }
        // Move to the right if passed value is 
        // greater than the current node
        else if(value > node.value){
          node.right = insert(node.right, value);
        }
        return node;
      }
        
      // Method to get height of the tree
      public int calculateTreeHeight(Node root){
        if(root == null){
          return 0;
        }else{
          // height of left subtree
          int lsh = calculateTreeHeight(root.left);
          // height of right subtree
          int rsh = calculateTreeHeight(root.right);
          // height in each recursive call
          return Math.max(lsh, rsh) + 1;
        }        
      }
        
      public void levelOrder(){
        int height = calculateTreeHeight(root);
        for(int i = 0; i < height; i++){
          levelOrderTraversal(root, i);
        }
      }
      // Recursive Method for breadth first search
      public void levelOrderTraversal(Node node, int level){
        if(node == null){
          return;
        }
        if(level == 0){
          System.out.print(node.value + " ");
        }else{
          levelOrderTraversal(node.left, level-1);
          levelOrderTraversal(node.right, level-1);
        }    
      }
        
      // Iterative method for breadth first search
      public void treeLevelOrderTraversal(Node root){
        if(root == null){
          return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
          Node node = queue.poll();
          System.out.print(node.value + " ");
          if(node.left != null){
            queue.add(node.left);
          }
          if(node.right != null){
            queue.add(node.right);
          }
        }
      }
        
      public static void main(String[] args) {
        BFS bst = new BFS();
        bst.insert(50);
        bst.insert(70);    
        bst.insert(30);
        bst.insert(15);
        bst.insert(35);
        bst.insert(7);
        bst.insert(22);
        bst.insert(31);
        bst.insert(62);
        bst.insert(87);
        System.out.println("Height- " + bst.calculateTreeHeight(bst.root));
        System.out.println("Level order traversal recursive");
        bst.levelOrder();
        System.out.println("");
        System.out.println("Level order traversal iterative");
        bst.treeLevelOrderTraversal(bst.root);
        System.out.println("");
      }
    }
    

    Output

    Height- 4
    Level order traversal recursive
    50 30 70 15 35 62 87 7 22 31 
    Level order traversal iterative
    50 30 70 15 35 62 87 7 22 31 
    

    That's all for this topic Binary Tree Traversal Using Breadth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

    >>>Return to Java Programs Page


    Related Topics

    1. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
    2. Counting Sort Program in Java
    3. Print Odd-Even Numbers Using Threads And wait-notify Java Program
    4. Find Duplicate Characters in a String With Repetition Count Java Program
    5. Armstrong Number or Not Java Program

    You may also like-

    1. Zipping Files And Folders in Java
    2. Java Lambda Expression Comparator Example
    3. How to Convert String to Date in Java
    4. Matrix Subtraction Java Program
    5. Batch Processing in Java JDBC - Insert, Update Queries as a Batch
    6. PermGen Space Removal in Java 8
    7. String Comparison in Java equals(), compareTo(), startsWith() Methods
    8. How to Inject Null And Empty String Values in Spring

    Wednesday, June 1, 2022

    Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program

    If we have to find the node with minimum value and node with maximum value in a binary search tree that is a simple operation because of the way binary search tree is structured.

    As we know in Binary search tree, for each node the node’s left child must have a value less than its parent node and the node’s right child must have a value greater than or equal to its parent. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node and the right subtree must have nodes with values greater than the root node.

    So the steps for finding the node with minimum value in a Binary search tree are as follows-

    1. Starting from the root node go to its left child.
    2. Keep traversing the left children of each node until a node with no left child is reached. That node is a node with minimum value.

    Same way steps for finding the node with maximum value in a Binary search tree are as follows-

    1. Starting from the root node go to its right child.
    2. Keep traversing the right children of each node until a node with no right child is reached. That node is a node with maximum value.

    Following image shows the traversal of nodes in a BST for minimum and maximum nodes.

    min max in BST

    Find nodes with min and max values in a BST – Java Program

    public class MinAndMaxBST {
      // first node
      private Node root;
      MinAndMaxBST(){
        root = null;
      }
      // Class representing tree nodes
      static class Node{
        int value;
        Node left;
        Node right;
        Node(int value){
          this.value = value;
          left = null;
          right = null;        
        }
        public void displayData(){
          System.out.print(value + " ");
        }
      }
        
      public void insert(int i){
        root = insert(root, i);
      }
        
      //Inserting node - recursive method
      public Node insert(Node node, int value){
        if(node == null){
          return new Node(value);
        }
        // Move to the left if passed value is 
        // less than the current node
        if(value < node.value){
          node.left = insert(node.left, value);
        }
        // Move to the right if passed value is 
        // greater than the current node
        else if(value > node.value){
          node.right = insert(node.right, value);
        }
        return node;
      }
        
      // For traversing in order
      public void inOrder(Node node){
        if(node != null){
          inOrder(node.left);
          node.displayData();
          inOrder(node.right);
        }
      }
      // Finding node with min value
      public Node findMinimum(Node node){
        if(node.left != null){
          return findMinimum(node.left);
        }
        return node;
      }
      // Finding node with max value    
      public Node findMaximum(Node node){
        if(node.right != null){
          return findMaximum(node.right);
        }
        return node;
      }
        
      public static void main(String[] args) {
        MinAndMaxBST bst = new MinAndMaxBST();
        bst.insert(50);
        bst.insert(70);        
        bst.insert(30);
        bst.insert(15);
        bst.insert(35);
        bst.insert(7);
        bst.insert(22);
        System.out.println("Inorder traversal of binary tree");
        bst.inOrder(bst.root);
        System.out.println();
        Node minNode = bst.findMinimum(bst.root);
        Node maxNode = bst.findMaximum(bst.root);
        System.out.println("Minimum node value- " + minNode.value);
        System.out.println("Maximum node value- " + maxNode.value);
      }
    }
    

    Output

    Inorder traversal of binary tree
    7 15 22 30 35 50 70 
    Minimum node value- 7
    Maximum node value- 70
    

    That's all for this topic Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

    >>>Return to Java Programs Page


    Related Topics

    1. Java Program to Delete a Node From Binary Search Tree (BST)
    2. Linked List Implementation Java Program
    3. Linear Search (Sequential Search) Java Program
    4. Convert Numbers to Words Java Program
    5. Count Number of Times Each Character Appears in a String Java Program

    You may also like-

    1. Reading File in Java Using BufferedReader
    2. Java Lambda Expression Callable Example
    3. How to Find Common Elements Between Two Arrays Java Program
    4. How to Compile Java Program at Runtime
    5. Reflection in Java - Getting Class Information
    6. Thread States (Thread Life Cycle) in Java Multi-Threading
    7. Try-With-Resources in Java With Examples
    8. Apache Avro Format in Hadoop