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

Tags: datastructure, data, structure, programming, binarysearchtree, bts, java

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}