Binary Search Tree (BTS) in Java and some of its common methods

dreamecho100

dreamecho100

Mazen Mohamed
created at: tags: data-structure, programming, binary-search-tree, bts, java
Binary Search Tree (BTS) in Java and some of its common methods

A binary Search Tree is a node-based binary tree data structure that has the following properties:

Values of keys in the left sub-tree of the root should be smaller than or equal to the values of the key at the root and the keys in the right sub-tree of the root should be larger than or equal to the values of the key at the root.

The left and right subtree each must also be a binary search tree.

Binary Search Tree (BTS) implementation in Java

Before starting with the linked list we will first need a class [ "Node" ] that has two attributes:

  • [ "data" ]: will hold the value
  • [ "right" ]: it will point to a [ "Node" ] if exist that its [ "data" ] is greater than the [ "data" ] on the [ "Node" ] on the left.
  • [ "right" ]: it will point to a [ "Node" ] if exist that its [ "data" ] is less than the [ "data" ] on the [ "Node" ] on the right.

Such a tree can be represented by a linked list data structure in which each node is an object.

In addition to a key field or data, each node contains fields (left pointer), and (right pointer), (parent pointer) that point to the nodes corresponding to its left child, its right child, and its parent, respectively.

If a child or a parent is missing, the appropriate field contains the value [ "null" ]. The root node is the only node in the tree whose parent field is [ "null" ].

1public class Node {
2 int data;
3 Node right, left;
4
5 public Node(int data) {
6  this.data = data;
7  right = left = null;
8 }
9
10 Node findNode(int value) {
11  // `tempNode` points at the first `Node` in the tree
12  Node tempNode = root;
13
14  // Continue to loop while `tempNode` exist and `tempNode.data` doesn't equal `value`
15  while (tempNode != null && tempNode.data != value) {
16  // Choosing the path to go to
17   if (value < tempNode.data)
18    tempNode = tempNode.left;
19   else
20    tempNode = tempNode.right;
21  }
22
23  // The returned value could be null if not found!
24  return tempNode;
25 }
26
27 boolean find(int value) {
28  // Check if the node with the desired `value` exists on the tree
29  return findNode(value) != null;
30 }
31
32 Node findParent(int value) {
33   // Similar to `findNode` method but we will keep
34   // track of the parent node and return it
35  Node current = root;
36  Node parent = null;
37
38  while (current != null && current.data != value) {
39   parent = current;
40
41   if (value < current.data)
42    current = current.left;
43   else
44    current = current.right;
45  }
46
47  // The returned value could be null if no root is found
48  // The parent could not have the value on their children
49  // but it is the best position to insert a `Node` with the `value` as its `data`
50  return parent;
51 }
52
53 // To get the most right `Node` (that holds the biggest value) on the tree
54 // by keeping looping until `Node.right` not equal `null`
55 Node getRightMostNode(Node node) {
56  Node rightMostNode = node;
57  while (rightMostNode.right != null)
58   rightMostNode = rightMostNode.right;
59
60  return rightMostNode;
61 }
62
63 // To get the most left `Node` (that holds the smallest value) on the tree
64 // by keeping looping until `Node.left` not equal `null`
65 Node getLeftMostNode(Node node) {
66  Node leftMostNode = node;
67  while (leftMostNode.left != null)
68   leftMostNode = leftMostNode.left;
69
70  return leftMostNode;
71 }
72}

then we will start with building the basic needs of the binary search tree.

1public class MyBinarySearchTree {
2 Node root;
3
4 public MyBinarySearchTree() {
5  root = null;
6 }
7
8 boolean isLeaf(Node node) {
9  return node.left == null && node.right == null;
10 }
11
12 boolean isParentWithOneChild(Node node) {
13  return (node.left == null && node.right != null) || (node.left != null && node.right == null);
14 }
15}
  • [ "root" ]: An attribute with [ "Node" ] that will point at the first [ "Node" ] in the tree.
  • [ "MyBinarySearchTree()" ]: A constructor that will assign [ "root" ] to null.
  • [ "isLeaf" ]: A method that takes [ "node" ] with the type of [ "Node" ] as an argument and will return a boolean, it will return true if [ "node.left" ] equals null and [ "node.right" ] equals null.
  • [ "isParentWithOneChild" ]: A method that takes [ "node" ] with the type of [ "Node" ] as an argument and will return a boolean, it will return true if it has only one child.
  • [ "findNode" ]: A method that returns a [ "Node" ] and takes a [ "value" ] as an argument with type [ "int" ]:
    • [ "tempNode" ] points at the first [ "Node" ] in the tree
    • Continue to loop while [ "tempNode" ] exist and [ "tempNode.data" ] doesn't equal [ "value" ]
    • Choosing the path to go to
    • The returned value could be null if not found!
  • [ "find" ]: A method that returns a [ "boolean" ] and takes a [ "value" ] as an argument with type [ "int" ]:
    • Check if the node with the desired [ "value" ] exists on the tree.
  • [ "findParent" ]: A method that returns a [ "Node" ] and takes a [ "value" ] as an argument with type [ "int" ]:
    • Similar to [ "findNode" ] method but we will keep track of the parent node and return it.
    • The returned value could be null if no root is found.
    • The parent could not have the value on its children but is in the best position to insert a [ "Node" ] with the [ "value" ] as its [ "data" ].
  • [ "getRightMostNode" ]: A method that accepts a [ "Node" ] (that holds the biggest value) and by keeping looping until [ "Node.right" ] does not equal [ "null" ] To get the most right [ "Node" ] on the tree
  • [ "getLefttMostNode" ]: A method that accepts a [ "Node" ] (that holds the smallest value) and by keeping looping until [ "Node.left" ] is not equal [ "null" ] To get the most left [ "Node" ] on the tree

Insert a node on the binary search tree implementation in Java

1void insert(int value) {
2  // Check if the `value` already exists in the `Node`s of the tree
3  Node current = findNode(value);
4  // Return if exist
5  if (current != null)
6    return;
7
8  // Building a `Node` with `value` as it's `data`
9  Node inserted = new Node(value);
10  // Find the suitable parent for it
11  Node parent = findParent(value);
12
13  // If No parent found then insert it as the root of the binary tree
14  // and return from the method
15  if (parent == null) {
16    root = inserted;
17    return;
18  }
19
20  // Insert it at the correct branch
21  if (value < parent.data)
22    parent.left = inserted;
23  else if (value > parent.data)
24    parent.right = inserted;
25}
  • Check if the [ "value" ] already exists in the [ "Node" ]s of the tree.
  • Return if exist.
  • Building a [ "Node" ] with [ "value" ] as its [ "data" ].
  • Find a suitable parent for it.
  • If No parent is found then insert it as the root of the binary tree and return from the method.
  • Insert it at the correct branch.
1#
2# 34, 86, 12, 98, 27, 9, 120, 3
3# ^^
4# Tree:
5#    ----
6#   | 34 |
7#    ----
8#
9# -------------------------------------------------------------------
10# 34, 86, 12, 98, 27, 9, 120, 3
11#     ^^
12#
13# Tree:
14#    ----------
15#   |    34    |
16#   |     \\   |
17#   |      86  |
18#    ----------
19#
20#
21# -------------------------------------------------------------------
22# 34, 86, 12, 98, 27, 9, 120, 3
23#         ^^
24#
25# Tree:
26#    ---------
27#   |    34   |
28#   |  //  \  |
29#   | 12   86 |
30#    ---------
31#
32# -------------------------------------------------------------------
33# 34, 86, 12, 98, 27, 9, 120, 3
34#             ^^
35#
36# Tree:
37#    ---------          ------------          --------------
38#   |    34   |        |     34     |        |      34      |
39#   |  /  \\  |        |    / \\    |        |     / \\     |
40#   | 12   86 |   ->   |   12  86   |   ->   |   12   86    |
41#    ---------          ------------         |         \\   |
42#                                            |          98  |
43#                                             --------------
44#
45# -------------------------------------------------------------------
46# 34, 86, 12, 98, 27, 9, 120, 3
47#                 ^^
48#
49# Tree:
50#    -------------          -------------          --------------
51#   |     34      |        |     34      |        |     34       |
52#   |    /  \     |        |    //  \    |        |    //  \     |
53#   |   12  86    |   ->   |   12   86   |   ->   |   12   86    |
54#   |         \   |        |         \   |        |    \\    \   |
55#   |         98  |        |         98  |        |     27   98  |
56#    -------------          -------------          --------------
57#
58# -------------------------------------------------------------------
59# 34, 86, 12, 98, 27, 9, 120, 3
60#                     ^
61#
62# Tree:
63#    -------------          -------------          ---------------
64#   |     34      |        |     34      |        |       34      |
65#   |    /  \     |        |   //  \     |        |     //  \     |
66#   |   12   86   |   ->   |  12   86    |   ->   |    12   86    |
67#   |    \     \  |        |    \    \   |        |   // \    \   |
68#   |     27   98 |        |    27   98  |        |  9   27   98  |
69#    -------------          -------------          ---------------
70#
71# -------------------------------------------------------------------
72# 34, 86, 12, 98, 27, 9, 120, 3
73#                        ^^^
74#
75# Tree:
76#    ---------------         ---------------          --------------          -------------------
77#   |      34      |        |      34       |        |      34      |        |         34        |
78#   |     /  \     |        |     / \\      |        |     / \\     |        |        / \\       |
79#   |    12  86    |        |    12   86    |        |    12   86   |        |      12   86      |
80#   |   / \    \   |   ->   |   / \     \   |   ->   |   / \    \\  |   ->   |     / \    \\     |
81#   |  9   27  98  |        |  9   27   98  |        |  9   27   98 |        |    9   27   98    |
82#    -------------           ---------------          --------------         |              \\   |
83#                                                                            |               120 |
84#                                                                             -------------------
85#
86# -------------------------------------------------------------------
87# 34, 86, 12, 98, 27, 9, 120, 3
88#                             ^
89#
90# Tree:
91#    -------------------          --------------------         -------------------         ----------------------
92#   |        34         |        |         34        |       |         34         |       |          34          |
93#   |       /  \        |        |       //  \       |       |       //  \        |       |        //  \         |
94#   |      12   86      |        |      12   86      |       |      12    86      |       |       12   86        |
95#   |     / \     \     |   ->   |     / \     \     |  ->   |     // \     \     |  ->   |      // \    \       |
96#   |    9   27   98    |        |    9   27   98    |       |    9   27    98    |       |     9   27   98      |
97#   |              \    |        |              \    |       |                \   |       |    //          \     |
98#   |              120  |        |              120  |       |                120 |       |   3            120   |
99#    -------------------          -------------------         --------------------         ----------------------
100#
101# -------------------------------------------------------------------
102#
103# Tree:
104#    ----------------------
105#   |          34          |
106#   |         /  \         |
107#   |        12  86        |
108#   |       /  \   \       |
109#   |      9   27  98      |
110#   |     /          \     |
111#   |    3           120   |
112#    ----------------------

Remove a node on the binary search tree implementation in Java

(Case 1) Remove a node on the binary search tree implementation in Java

node [ "n" ] has no children (a terminal node): In this case, [ "n" ] is deleted and replaced with its location in the parent node to the NULL pointer.

(Case 2) Remove a node on the binary search tree implementation in Java

N has exactly one child: [ "n" ] is deleted from the tree T by replacing the pointer to [ "n" ] in Parent[N] with the pointer to the child of [ "n" ].

(Case 3) Remove a node on the binary search tree implementation in Java

N has two children : let [ "S(N)" ] denotes the in-order successor of [ "n" ]. Deleting [ "n" ] is performed by - First deleting [ "S(N)" ] and replacing [ "n" ] with [ "S(N)" ] as in figure (a). - Change the pointer of the parent of [ "S(N)" ] to the right child of [ "S(N)" ]. See Figure 7-10(b). - Add [ "S(N)" ] to the free-storage list denoted by the AVAIL pointer, see

1int remove(int value) {
2  // We will save the value of the deleted `Node`
3  int deletedValue;
4  // Using the `findNode` method to find the deleted `Node`
5  Node deletedNode = findNode(value);
6  // Using the `findParent` method to find the parent of the deleted `Node`
7  Node parent = findParent(value);
8
9  if (deletedNode == null) {
10    // If there is no `Node` that have the desired value we exit
11    System.err.println("Node not found!");
12    System.exit(1);
13  }
14
15  // Else We will check if the `Node` is a **leaf**
16  if (isLeaf(deletedNode)) {
17  // If true we will check where it is it and assignning it to `null` to delete it
18  if (deletedNode == root)
19    root = null;
20  else {
21  if (parent.left == deletedNode)
22    parent.left = null;
23  else
24    parent.right = null;
25  }
26
27  deletedValue = deletedNode.data;
28  } else if (isParentWithOneChild(deletedNode)) {
29    // Else if it is not a `leaf`, we will check if the parent
30    // has one child _either on the left or the right_
31    // Then swaping its position with it child _`Node` not equal `null`_
32    // After that we assignning it to `null` to delete it
33    if (parent.right == deletedNode) {
34    if (deletedNode.right != null)
35      parent.right = deletedNode.right;
36    else
37      parent.left = deletedNode.left;
38    } else {
39    if (deletedNode.right != null)
40      parent.right = deletedNode.right;
41    else
42      parent.left = deletedNode.left;
43    }
44
45    deletedValue = deletedNode.data;
46  } else {
47    // If it is not a leaf or the parent does not have one child
48    // Then we will get the `Node` with the largest value on the tree
49    // (In the right most of the tree) to delete it
50    Node highestLeftNode = getRightMostNode(deletedNode.left);
51    deletedValue = remove(highestLeftNode.data);
52    deletedNode.data = deletedValue;
53  }
54
55  return value;
56}
  • We will save the value of the deleted [ "Node" ].
  • Using the [ "findNode" ] method to find the deleted [ "Node" ].
  • Using the [ "findParent" ] method to find the parent of the deleted [ "Node" ].
    • If there is no [ "Node" ] that have the desired value we exit.
  • Else We will check if the [ "Node" ] is a leaf.
  • If true we will check where it is it and assignning it to [ "null" ] to delete it.
  • Else if it is not a [ "leaf" ], we will check if the parent has one child either on the left or the right.
    • Then swaping its position with it child [ "Node" ] not equal [ "null" ].
    • After that we assignning it to [ "null" ] to delete it.
  • If it is not a leaf or the parent does not have one child.
    • Then we will get the [ "Node" ] with the largest value on the tree (In the right most of the tree) to delete it.
1
2# 9, 27, 120
3# ^
4#9
5# Tree:
6#    ----------------------          ----------------------          ----------------------
7#   |         34           |        |         34           |        |         34           |
8#   |        //  \         |        |        //  \         |        |        //  \         |
9#   |       12   86        |        |       12   86        |        |       12   86        |
10#   |      /  \    \       |   ->   |      // \    \       |   ->   |      /  \    \       |
11#   |     9   27   98      |        |     9   27   98      |        |     3   27   98      |
12#   |    /           \     |        |    /           \     |        |                \     |
13#   |   3            120   |        |   3            120   |        |                120   |
14#    ----------------------          ----------------------          ----------------------
15#
16# -------------------------------------------------------------------
17#
18# 9, 27, 120
19#    ^^
20#
21#    ---------------------          ---------------------          ---------------------          ---------------------
22#   |         34          |        |         34          |        |         34          |        |         34          |
23#   |        /   \        |        |        //  \        |        |        //  \        |        |        /   \        |
24#   |       12   86       |        |       12   86       |        |       12   86       |        |       12   86       |
25#   |      /  \    \      |   ->   |      /  \    \      |   ->   |      / \\    \      |   ->   |      /       \      |
26#   |     3   27   98     |        |     3   27   98     |        |     3   27   98     |        |     3        98     |
27#   |                \    |        |                \    |        |                \    |        |                \    |
28#   |                120  |        |                120  |        |                120  |        |                120  |
29#    ---------------------          ---------------------          ---------------------          ---------------------
30#
31# -------------------------------------------------------------------
32#
33# 9, 27, 120
34#        ^^^
35#
36#    ---------------------          ---------------------          ---------------------          ---------------------          ---------------------          ---------------------
37#   |         34          |        |         34          |        |         34          |        |         34          |        |         34          |        |         34          |
38#   |        /   \        |        |        /   \        |        |        /  \\        |        |        /  \\        |        |        /  \\        |        |        /  \\        |
39#   |       12   86       |        |       12   86       |        |       12   86       |        |       12   86       |        |       12   86       |        |       12   86       |
40#   |      /       \      |   ->   |      /       \      |   ->   |      /       \      |   ->   |      /      \\      |   ->   |      /      \\      |   ->   |      /      \\      |
41#   |     3        98     |        |     3        98     |        |     3        98     |        |     3        98     |        |     3        98     |        |     3        98     |
42#   |                \    |        |                \    |        |                \    |        |                \    |        |               \\    |         ---------------------
43#   |                120  |        |                120  |        |                120  |        |                120  |        |                120  |
44#    ---------------------          ---------------------          ---------------------          ---------------------          ---------------------

print inOrder, preOrder, and postOrder on the binary search tree implementation in Java

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc), which have only one logical way to traverse them, trees can be traversed in different ways.

We will discuss the most generally used ways for traversing trees.

1void print(int order) {
2  switch (order) {
3    case 1:
4      System.out.println("nInorder traversal of binary tree is:");
5      printInOrder(root);
6      break;
7    case 2:
8      System.out.println("Preorder traversal of binary tree is:");
9      printPreOrder(root);
10      break;
11    case 3:
12      System.out.println("nPostorder traversal of binary tree is:");
13      printPostOrder(root);
14      break;
15    default:
16      break;
17  }
18}
19
20// Given a binary tree, print its nodes in inorder
21void printInOrder(Node currentNode) {
22  if (currentNode == null)
23    return;
24
25  // First recur on left child
26  printInOrder(currentNode.left);
27  // Then print the data of node
28  System.out.println(currentNode.data);
29  // Now recur on right child
30  printInOrder(currentNode.right);
31}
32
33// Given a binary tree, print its nodes in preorder
34void printPreOrder(Node currentNode) {
35  if (currentNode == null)
36    return;
37
38  // First print data of node
39  System.out.println(currentNode.data);
40  // Then recur on left subtree
41  printPreOrder(currentNode.left);
42  // Now recur on right subtree
43  printPreOrder(currentNode.right);
44}
45
46// Given a binary tree, print its nodes according to the "bottom-up" postorder traversal.
47void printPostOrder(Node currentNode) {
48  if (currentNode == null)
49    return;
50
51  // First recur on left subtree
52  printPostOrder(currentNode.left);
53  // Then recur on right subtree
54  printPostOrder(currentNode.right);
55  // Now deal with the node
56  System.out.println(currentNode.data);
57}

Depth First Traversals:

we will use the following example: If we insert [ "34, 86, 12, 98, 27, 9, 120, 3" ] to the tree.

1# Tree:
2#    ----------------------
3#   |          34          |
4#   |         /  \         |
5#   |        12  86        |
6#   |       /  \   \       |
7#   |      9   27  98      |
8#   |     /          \     |
9#   |    3           120   |
10#    ----------------------
  • Preorder (Root, Left, Right): [ "34, 12, 9, 3, 27 86,98, 120" ].
  • Inorder (Left, Root, Right): [ "3, 9, 12, 27, 34, 86, 98, 120" ].
  • Postorder (Left, Right, Root): [ "3, 9, 27, 12, 120, 98, 86, 34" ].

Inorder(tree) Traversal Algorithm

  1. Traverse the left subtree, ex. call [ "Inorder(left-subtree)" ].
  2. Visit the root.
  3. Traverse the right subtree, ex. call [ "Inorder(right-subtree)" ].
Uses of Inorder

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.

It provides a simple way to print out all the keys in a Binary Search Tree in an ascending order

To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used.

Example: In order traversal for the given example is [ "3, 9, 12, 27, 34, 86, 98, 120" ].

Preorder(tree) Traversal Algorithm

  1. Visit the root.
  2. Traverse the left subtree, ex. call [ "Preorder(left-subtree)" ].
  3. Traverse the right subtree, ex. call [ "Preorder(right-subtree)" ].
Uses of Preorder

Preorder traversal is used to create a copy of the tree.

Preorder traversal is also used to get prefix expression on an expression tree.

Example: Preorder traversal for the given example is [ "34, 12, 9, 3, 27 86, 98, 120" ].

Postorder(tree) Traversal Algorithm

  1. Traverse the left subtree, ex. call [ "Postorder(left-subtree)" ].
  2. Traverse the right subtree, ex. call [ "Postorder(right-subtree)" ].
  3. Visit the root.
Uses of Postorder

Postorder traversal is used to delete the tree.

Example: Postorder traversal for the given example is [ "3, 9, 27, 12, 120, 98, 86, 34" ].

1public class Main {
2
3 public static void main(String[] args) {
4  MyBinarySearchTree myBSTTree = new MyBinarySearchTree();
5
6  // 34, 86, 12, 98, 27, 9, 120, 3
7  myBSTTree.insert(34);
8  myBSTTree.insert(86);
9  myBSTTree.insert(12);
10  myBSTTree.insert(98);
11  myBSTTree.insert(27);
12  myBSTTree.insert(9);
13  myBSTTree.insert(120);
14  myBSTTree.insert(3);
15
16  myBSTTree.print(1);
17  myBSTTree.print(2);
18  myBSTTree.print(3);
19 }
20
21}
1# Tree:
2#    ----------------------
3#   |          34          |
4#   |         /  \         |
5#   |        12  86        |
6#   |       /  \   \       |
7#   |      9   27  98      |
8#   |     /          \     |
9#   |    3           120   |
10#    ----------------------
1# Preorder traversal of binary tree is:
2# 34
3# 12
4# 9
5# 3
6# 27
7# 86
8# 98
9# 120
10# Inorder traversal of binary tree is:
11# 3
12# 9
13# 12
14# 27
15# 34
16# 86
17# 98
18# 120
19# Postorder traversal of binary tree is:
20# 3
21# 9
22# 27
23# 12
24# 120
25# 98
26# 86
27# 34
1public class Main {
2 public static void main(String[] args) {
3  MyBinarySearchTree myBSTTree = new MyBinarySearchTree();
4
5  // 34, 86, 12, 98, 27, 9, 120, 3
6  myBSTTree.insert(34);
7  myBSTTree.insert(86);
8  myBSTTree.insert(12);
9  myBSTTree.insert(98);
10  myBSTTree.insert(27);
11  myBSTTree.insert(9);
12  myBSTTree.insert(120);
13  myBSTTree.insert(3);
14
15  // 9, 27, 120
16  myBSTTree.remove(9);
17  myBSTTree.remove(27);
18  myBSTTree.remove(120);
19
20  myBSTTree.print(1);
21  myBSTTree.print(2);
22  myBSTTree.print(3);
23 }
24}
1# Tree:
2#    ---------------------
3#   |         34          |
4#   |        /  \         |
5#   |       12   86       |
6#   |      /      \       |
7#   |     3        98     |
8#    ---------------------
1# Preorder traversal of binary tree is:
2# 34
3# 12
4# 3
5# 86
6# 98
7# Inorder traversal of binary tree is:
8# 3
9# 12
10# 34
11# 86
12# 98
13# Postorder traversal of binary tree is:
14# 3
15# 12
16# 98
17# 86
18# 34

Complexity of BST

O(log2 [ "n" ]), Where [ "n" ] is the total number of nodes in BST

Final Code

1public class Node {
2 int data;
3 Node right, left;
4
5 public Node(int data) {
6  this.data = data;
7  right = left = null;
8 }
9}
1public class MyBinarySearchTree {
2 Node root;
3
4 public MyBinarySearchTree() {
5  root = null;
6 }
7
8 boolean isLeaf(Node node) {
9  return node.left == null && node.right == null;
10 }
11
12 boolean isParentWithOneChild(Node node) {
13  return (node.left == null && node.right != null) || (node.left != null && node.right == null);
14 }
15
16 Node findNode(int value) {
17  Node tempNode = root;
18
19  while (tempNode != null && tempNode.data != value) {
20   if (value < tempNode.data)
21    tempNode = tempNode.left;
22   else
23    tempNode = tempNode.right;
24  }
25
26  return tempNode;
27 }
28
29 boolean find(int value) {
30  return findNode(value) != null;
31 }
32
33 Node findParent(int value) {
34  Node current = root;
35  Node parent = null;
36
37  while (current != null && current.data != value) {
38   parent = current;
39
40   if (value < current.data)
41    current = current.left;
42   else
43    current = current.right;
44  }
45
46  return parent;
47 }
48
49 Node getRightMostNode(Node node) {
50  Node rightMostNode = node;
51  while (rightMostNode.right != null)
52   rightMostNode = rightMostNode.right;
53
54  return rightMostNode;
55 }
56
57 Node getLeftMostNode(Node node) {
58  Node leftMostNode = node;
59  while (leftMostNode.left != null)
60   leftMostNode = leftMostNode.left;
61
62  return leftMostNode;
63 }
64
65 void insert(int value) {
66  Node current = findNode(value);
67  if (current != null)
68   return;
69
70  Node inserted = new Node(value);
71  Node parent = findParent(value);
72
73  if (parent == null) {
74   root = inserted;
75   return;
76  }
77
78  if (value < parent.data)
79   parent.left = inserted;
80  else if (value > parent.data)
81   parent.right = inserted;
82 }
83
84 int remove(int value) {
85  int deletedValue;
86  Node deletedNode = findNode(value);
87  Node parent = findParent(value);
88
89  if (deletedNode == null) {
90   System.err.println("Node not found!");
91   System.exit(1);
92  }
93
94  if (isLeaf(deletedNode)) {
95   if (deletedNode == root)
96    root = null;
97   else {
98    if (parent.left == deletedNode)
99     parent.left = null;
100    else
101     parent.right = null;
102   }
103
104   deletedValue = deletedNode.data;
105  } else if (isParentWithOneChild(deletedNode)) {
106   if (parent.right == deletedNode) {
107    if (deletedNode.right != null)
108     parent.right = deletedNode.right;
109    else
110     parent.left = deletedNode.left;
111   } else {
112    if (deletedNode.right != null)
113     parent.right = deletedNode.right;
114    else
115     parent.left = deletedNode.left;
116   }
117
118   deletedValue = deletedNode.data;
119  } else {
120   Node highestLeftNode = getRightMostNode(deletedNode.left);
121   deletedValue = remove(highestLeftNode.data);
122   deletedNode.data = deletedValue;
123  }
124
125  return value;
126 }
127
128 void print(int order) {
129  switch (order) {
130  case 1:
131   System.out.println("Preorder traversal of binary tree is:");
132   printPreOrder(root);
133   break;
134  case 2:
135   System.out.println("Inorder traversal of binary tree is:");
136   printInOrder(root);
137   break;
138  case 3:
139   System.out.println("Postorder traversal of binary tree is:");
140   printPostOrder(root);
141   break;
142  default:
143   break;
144  }
145 }
146
147 void printPreOrder(Node currentNode) {
148  if (currentNode == null)
149   return;
150
151  System.out.println(currentNode.data);
152  printPreOrder(currentNode.left);
153  printPreOrder(currentNode.right);
154 }
155
156 void printInOrder(Node currentNode) {
157  if (currentNode == null)
158   return;
159
160  printInOrder(currentNode.left);
161  System.out.println(currentNode.data);
162  printInOrder(currentNode.right);
163 }
164
165 void printPostOrder(Node currentNode) {
166  if (currentNode == null)
167   return;
168
169  printPostOrder(currentNode.left);
170  printPostOrder(currentNode.right);
171  System.out.println(currentNode.data);
172 }
173}