Binary Search Tree and Tree Traversal - Inorder, Preorder, Postorder implemented in Java
Binary Search Tree and Tree Traversal – Inorder, Preorder, Postorder implemented in Java Most of the students fresh out of their engineering studies or those who are still studying will have the concept of Binary Search Trees fresh in their minds. But with most of the people who have been out of college for many years now will kind of be having a not so clear idea of Binary Search trees unless they have been using it or related concepts at their work. In this tutorial I would show how to implement a Binary Search Tree (BST) in Java and also show the following operations: Inserting/Building a BST Inorder Traversal of BST Preorder Traversal of BST Postorder Traversal of BST What is a Binary Search Tree (BST)? Binary Search Tree (BST) is a binary tree data structure with a special feature where in the value store at each node is greater than or equal to the value stored at its left sub child and lesser than the value stored at its right sub child. Lets look at an example of a BST:
Building a Binary Search Tree (BST)
- See more at: http://www.javabeat.net/binary-search-tree-traversal-java/#sthash.67ynYXf8.dpuf
Finding Maximum and Minimum Value in BST
- See more at: http://www.javabeat.net/binary-search-tree-traversal-java/#sthash.67ynYXf8.dpuf
Read full article from Binary Search Tree and Tree Traversal - Inorder, Preorder, Postorder implemented in Java
Binary Search Tree and Tree Traversal – Inorder, Preorder, Postorder implemented in Java Most of the students fresh out of their engineering studies or those who are still studying will have the concept of Binary Search Trees fresh in their minds. But with most of the people who have been out of college for many years now will kind of be having a not so clear idea of Binary Search trees unless they have been using it or related concepts at their work. In this tutorial I would show how to implement a Binary Search Tree (BST) in Java and also show the following operations: Inserting/Building a BST Inorder Traversal of BST Preorder Traversal of BST Postorder Traversal of BST What is a Binary Search Tree (BST)? Binary Search Tree (BST) is a binary tree data structure with a special feature where in the value store at each node is greater than or equal to the value stored at its left sub child and lesser than the value stored at its right sub child. Lets look at an example of a BST:
Building a Binary Search Tree (BST)
public class BinarySearchTree { |
2 | public Node root; |
3 |
4 | public void insert( int value){ |
5 | Node node = new Node<>(value); |
6 |
7 | if ( root == null ) { |
8 | root = node; |
9 | return ; |
10 | } |
11 |
12 | insertRec(root, node); |
13 |
14 | } |
15 |
16 | private void insertRec(Node latestRoot, Node node){ |
17 |
18 | if ( latestRoot.value > node.value){ |
19 |
20 | if ( latestRoot.left == null ){ |
21 | latestRoot.left = node; |
22 | return ; |
23 | } |
24 | else { |
25 | insertRec(latestRoot.left, node); |
26 | } |
27 | } |
28 | else { |
29 | if (latestRoot.right == null ){ |
30 | latestRoot.right = node; |
31 | return ; |
32 | } |
33 | else { |
34 | insertRec(latestRoot.right, node); |
35 | } |
36 | } |
37 | } |
38 | } |
Finding Maximum and Minimum Value in BST
public int findMinimum(){ |
5 | if ( root == null ){ |
6 | return 0 ; |
7 | } |
8 | Node currNode = root; |
9 | while (currNode.left != null ){ |
10 | currNode = currNode.left; |
11 | } |
12 | return currNode.value; |
13 | } |
14 |
15 | /** |
16 | * Returns the maximum value in the Binary Search Tree |
17 | */ |
18 | public int findMaximum(){ |
19 | if ( root == null ){ |
20 | return 0 ; |
21 | } |
22 |
23 | Node currNode = root; |
24 | while (currNode.right != null ){ |
25 | currNode = currNode.right; |
26 | } |
27 | return currNode.value; |
28 | } |
Read full article from Binary Search Tree and Tree Traversal - Inorder, Preorder, Postorder implemented in Java