Java program to implement Binary Search Tree and its Preorder, InOrder & Postorder traversal algorithms

Binary Search Tree

A binary tree is defined as a tree where each node can have no more than two children.

A binary search tree is a binary tree in which for every node, X, in the tree, the values of all the items in its left subtree are smaller than the item in X, and the values of all the items in its right subtree are larger than the item in X.

Inserting to a Binary Search Tree

To insert a node X into a binary search tree T, If the root is null, insert item at root. Else, we make a recursive call on a subtree of T, either left or right, depending on the relationship of X to the item stored in T.
If X is found, do nothing, otherwise, insert X at the last spot on the path traversed.

package com.topjavatutorial.app;

public class BinarySearchTree {

  public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree(30);
    int[] a = { 35, 57, 15, 63, 49, 89, 77, 67, 98, 91 };
    for (int n : a)
      bst.insert(n);
  }

  int data;
  BinarySearchTree left;
  BinarySearchTree right;

  public BinarySearchTree(int i) {
    this.data = i;
    this.left = null;
    this.right = null;
  }

  public void insert(int i) {
    if (i < this.data) {
      if (this.left != null)
        this.left.insert(i);
      else
        this.left = new BinarySearchTree(i);
    } else {
      if (this.right != null) {
        this.right.insert(i);
      } else {
        this.right = new BinarySearchTree(i);
      }
    }
  }
}

Binary Search Tree Traversal Algorithms

There are three traversal methods used with Binary Search Tree: inorder, preorder, and postorder.

– An inorder traversal visits all the nodes in a BST in ascending order of the node key values.
– A preorder traversal visits the root node first, followed by the nodes in the subtrees under the left child of the root, followed by the nodes in the subtrees under the right child of the root
– A postorder traversal, the method first recurses over the left subtrees and then over the right subtrees.

  // PreOrder Traversal : visit the node first, then left and right sub-trees
  public void traversePreOrder() {
    System.out.print(this.data + " ");
    if (this.left != null) {
      this.left.traversePreOrder();
    }
    if (this.right != null) {
      this.right.traversePreOrder();
    }
  }

  // InOrder Traversal : Visit left sub-tree, then node and then, right sub-tree
  public void traverseInOrder() {
    if (this.left != null) {
      this.left.traverseInOrder();
    }
    System.out.print(this.data + " ");
    if (this.right != null) {
      this.right.traverseInOrder();
    }
  }

  // PostOrder Traversal : Visit left sub-tree, then right sub-tree and then the node
  public void traversePostOrder() {
    if (this.left != null) {
      this.left.traversePostOrder();
    }
    if (this.right != null) {
      this.right.traversePostOrder();
    }
    System.out.print(this.data + " ");
  }

Here is the complete program :

package com.topjavatutorial.app;

public class BinarySearchTree {

  public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree(30);
    int[] a = { 35, 57, 15, 63, 49, 89, 77, 67, 98, 91 };
    for (int n : a)
      bst.insert(n);
    System.out.println("Preorder Traversal :");
    bst.traversePreOrder();

    System.out.println("\nInorder Traversal :");
    bst.traverseInOrder();

    System.out.println("\nPostorder Traversal :");
    bst.traversePostOrder();
  }

  int data;
  BinarySearchTree left;
  BinarySearchTree right;

  public BinarySearchTree(int i) {
    this.data = i;
    this.left = null;
    this.right = null;
  }

  public void insert(int i) {
    if (i < this.data) {
      if (this.left != null)
        this.left.insert(i);
      else
        this.left = new BinarySearchTree(i);
    } else {
      if (this.right != null) {
        this.right.insert(i);
      } else {
        this.right = new BinarySearchTree(i);
      }
    }
  }

  // PreOrder Traversal : visit the node first, then left and right sub-trees
  public void traversePreOrder() {
    System.out.print(this.data + " ");
    if (this.left != null) {
      this.left.traversePreOrder();
    }
    if (this.right != null) {
      this.right.traversePreOrder();
    }
  }

  // InOrder Traversal : Visit left sub-tree, then node and then, right sub-tree
  public void traverseInOrder() {
    if (this.left != null) {
      this.left.traverseInOrder();
    }
    System.out.print(this.data + " ");
    if (this.right != null) {
      this.right.traverseInOrder();
    }
  }

  // PostOrder Traversal : Visit left sub-tree, then right sub-tree and then the node
  public void traversePostOrder() {
    if (this.left != null) {
      this.left.traversePostOrder();
    }
    if (this.right != null) {
      this.right.traversePostOrder();
    }
    System.out.print(this.data + " ");
  }

}

Output:

Inorder Traversal :
15 30 35 49 57 63 67 77 89 91 98
Preorder Traversal :
30 15 35 57 49 63 89 77 67 98 91
Postorder Traversal :
15 49 67 77 91 98 89 63 57 35 30

© 2017, https:. All rights reserved. On republishing this post, you must provide link to original post