1. What is Binary Tree
A binary tree is data structure where each node can have 2 children at most.
2. When binary tree is a binary search tree ?
Binary tree is a binary search tree, when
- Every node’s value is greater than or equal to the left sub-tree’s node values, and
- less than or equal to the node values in the right sub-tree.
3. Inserting node (or Elements)
- when current node is null, insert the new node in that position
- if new node’s value is lower than the current node’s value, go to left child
- if new node’s value is greater than the current node’s, go to right child
4. Deleting node
Once we find the node to delete, there are 3 main different cases:
- When node has no children – replace this node with null in its parent node.
- When node has exactly one child – in the parent node, we replace this node with its only child.
- When node has two children – re organize tree
5. Traversing the Tree
5.1. Depth-First Search (dfs) in binary tree in java
Depth-first search is a type of traversal that goes deep as much as possible in every child before exploring the next sibling.
3 types of depth first search
PreOrder traversal of Binary Tree in java
Steps in PreOrder Traversal of Binary Tree in java -
- Visit the node.
- Traverse the left subtree.
- Traverse the right subtree.
preOrder
50 17 12 9 14 23 19 72 54 67 76
InOrder traversal of Binary Tree in java
Steps in InOrder Traversal of Binary Tree in java -
- Traverse the left subtree
- Visit the node.
- Traverse the right subtree.
inOrder
9 12 14 17 19 23 50 54 67 72 76
PostOrder traversal of Binary Tree in java
Steps in PostOrder Traversal of Binary Tree in java -
- traverse left subtree
- traverse the right subtree.
- Visit the node.
postOrder
9 14 12 19 23 17 67 54 76 72 50
5.2. Breadth-First Search (level order) (bfs) in binary tree in java
visits all the nodes of a same level left to right before going to the next level.
Breadth-First Search
50 17 72 12 23 54 76 9 14 19 67
6. Full program/ example to show Binary Search Tree (bst) in java >
import java.io.IOException;
import java.util.Stack;
class Node {
public int value;
public Node leftChild;
public Node rightChild;
public String toString() {
return "id=" + value;
}
@Overridepublic String toString() {//return "[value=" + value + ", left=" + leftChild + ", right=" + rightChild + "]";return "[value=" + value +"]";}
}
class Tree {
public Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
} // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while (current.value != key) // while no match,
{
if (key < current.value) // go left?
current = current.leftChild;
else
// or go right?
current = current.rightChild;
if (current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id) {
Node newNode = new Node(); // make new node
newNode.value = id; // insert data
if (root == null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while (true) // (exits internally)
{
parent = current;
if (id < current.value) // go left?
{
current = current.leftChild;
if (current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if (current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while (current.value != key) // search for node
{
parent = current;
if (key < current.value) // go left?
{
isLeftChild = true;
current = current.leftChild;
} else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if (current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// 1) if no children, simply delete it
if (current.leftChild == null && current.rightChild == null) {
if (current == root) // if root,
root = null; // tree is empty
else if (isLeftChild)
parent.leftChild = null; // disconnect
else
// from parent
parent.rightChild = null;
}
// 2.1) if no right child, replace with left subtree
else if (current.rightChild == null)
if (current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// 2.2) if no left child, replace with right subtree
else if (current.leftChild == null)
if (current == root)
root = current.rightChild;
else if (isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // 3) two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if (current == root)
root = successor;
else if (isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode) {
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while (current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if (successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public void preOrder(Node localRoot) {
if (localRoot != null) {
System.out.print(localRoot.value + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
public void inOrder(Node localRoot) {
if (localRoot != null) {
inOrder(localRoot.leftChild);
System.out.print(localRoot.value + " ");
inOrder(localRoot.rightChild);
}
}
public void postOrder(Node localRoot) {
if (localRoot != null) {
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.value + " ");
}
}
// Breadth-First Search //Display output in tree form
public void displayTree() {
Stack parentStack = new Stack();
parentStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
while (isRowEmpty == false) {
Stack childStack = new Stack();
isRowEmpty = true;
for (int j = 0; j < nBlanks; j++)
System.out.print(' ');
while (parentStack.isEmpty() == false) {
Node currentNode = (Node) parentStack.pop();
if (currentNode != null) {
System.out.print(currentNode.value);
childStack.push(currentNode.leftChild);
childStack.push(currentNode.rightChild);
if (currentNode.leftChild != null || currentNode.rightChild != null)
isRowEmpty = false;
} else {
System.out.print("--");
childStack.push(null);
childStack.push(null);
}
for (int j = 0; j < nBlanks * 2 - 2; j++)
System.out.print(' ');
} // end while parentStack not empty
System.out.println();
nBlanks /= 2;
while (childStack.isEmpty() == false)
parentStack.push(childStack.pop());
} // end while isRowEmpty is false
}
// Breadth-First Search // Simply- without formatting
public void displayTree2() {
Stack parentStack = new Stack();
parentStack.push(root);
boolean noChild = false;
while (noChild == false) {
Stack childStack = new Stack();
noChild = true; // Initially true, we will iterate till its false
while (parentStack.isEmpty() == false) {
Node currentNode = (Node) parentStack.pop();
if (currentNode != null) {
System.out.print(currentNode.value + " ");
childStack.push(currentNode.leftChild);
childStack.push(currentNode.rightChild);
// Find any any child exists or not OR
//If any of the left or right child is not null
if (currentNode.leftChild != null || currentNode.rightChild != null)
noChild = false; // It was set true at start of while loop and will
// remain true if no child exists
}
}
while (childStack.isEmpty() == false)
parentStack.push(childStack.pop());
} // end while isRowEmpty is false
System.out.println();
}
}
public class BinaryTree_BinarySearchTree_ExampleJava {
public static void main(String[] args) throws IOException {
// Insert
Tree theTree = new Tree();
theTree.insert(50);
theTree.insert(17);
theTree.insert(72);
theTree.insert(12);
theTree.insert(23);
theTree.insert(54);
theTree.insert(76);
theTree.insert(9);
theTree.insert(14);
theTree.insert(19);
theTree.insert(67);
// Breadth-First Search //Display output in tree form
System.out.println("Breadth-First Search //Display output in tree form");
theTree.displayTree();
// Breadth-First Search // Simply- without formatting
System.out.println("\nBreadth-First Search");
theTree.displayTree2();
// Depth first search
System.out.println("preOrder");
theTree.preOrder(theTree.root);
System.out.println("\ninOrder");
theTree.inOrder(theTree.root);
System.out.println("\npostOrder");
theTree.postOrder(theTree.root);
// Find
Node found = theTree.find(19);
if (found != null) {
System.out.print("\nFound");
} else
System.out.print("\nNot found ");
System.out.print("\n");
// Delete
boolean didDelete = theTree.delete(19);
if (didDelete)
System.out.println("Deleted ");
else
System.out.println("Could not delete ");
}
}
//output
/*
Breadth-First Search //Display output in tree form
50
17 72
12 23 54 76
9 14 19 -- -- 67 -- --
Breadth-First Search
50 17 72 12 23 54 76 9 14 19 67
preOrder
50 17 12 9 14 23 19 72 54 67 76
inOrder
9 12 14 17 19 23 50 54 67 72 76
postOrder
9 14 12 19 23 17 67 54 76 72 50
Found
Deleted
*/
|
Having any doubt? or you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.