Created
July 26, 2019 01:54
-
-
Save dfparker2002/99ceb637b96b7ba843087e9194bfd32e to your computer and use it in GitHub Desktop.
BinaryTree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//src: https://github.com/eugenp/tutorials/blob/5b5733239c06b595649324d744e97c6a2dc97d68/data-structures/src/main/java/com/baeldung/tree/BinaryTree.java | |
import java.util.LinkedList; | |
import java.util.Queue; | |
import java.util.Stack; | |
public class BinaryTree { | |
Node root; | |
public void add(int value) { | |
root = addRecursive(root, value); | |
} | |
private Node addRecursive(Node current, int value) { | |
if (current == null) { | |
return new Node(value); | |
} | |
if (value < current.value) { | |
current.left = addRecursive(current.left, value); | |
} else if (value > current.value) { | |
current.right = addRecursive(current.right, value); | |
} | |
return current; | |
} | |
public boolean isEmpty() { | |
return root == null; | |
} | |
public int getSize() { | |
return getSizeRecursive(root); | |
} | |
private int getSizeRecursive(Node current) { | |
return current == null ? 0 : getSizeRecursive(current.left) + 1 + getSizeRecursive(current.right); | |
} | |
public boolean containsNode(int value) { | |
return containsNodeRecursive(root, value); | |
} | |
private boolean containsNodeRecursive(Node current, int value) { | |
if (current == null) { | |
return false; | |
} | |
if (value == current.value) { | |
return true; | |
} | |
return value < current.value | |
? containsNodeRecursive(current.left, value) | |
: containsNodeRecursive(current.right, value); | |
} | |
public void delete(int value) { | |
root = deleteRecursive(root, value); | |
} | |
private Node deleteRecursive(Node current, int value) { | |
if (current == null) { | |
return null; | |
} | |
if (value == current.value) { | |
// Case 1: no children | |
if (current.left == null && current.right == null) { | |
return null; | |
} | |
// Case 2: only 1 child | |
if (current.right == null) { | |
return current.left; | |
} | |
if (current.left == null) { | |
return current.right; | |
} | |
// Case 3: 2 children | |
int smallestValue = findSmallestValue(current.right); | |
current.value = smallestValue; | |
current.right = deleteRecursive(current.right, smallestValue); | |
return current; | |
} | |
if (value < current.value) { | |
current.left = deleteRecursive(current.left, value); | |
return current; | |
} | |
current.right = deleteRecursive(current.right, value); | |
return current; | |
} | |
private int findSmallestValue(Node root) { | |
return root.left == null ? root.value : findSmallestValue(root.left); | |
} | |
public void traverseInOrder(Node node) { | |
if (node != null) { | |
traverseInOrder(node.left); | |
System.out.print(" " + node.value); | |
traverseInOrder(node.right); | |
} | |
} | |
public void traversePreOrder(Node node) { | |
if (node != null) { | |
System.out.print(" " + node.value); | |
traversePreOrder(node.left); | |
traversePreOrder(node.right); | |
} | |
} | |
public void traversePostOrder(Node node) { | |
if (node != null) { | |
traversePostOrder(node.left); | |
traversePostOrder(node.right); | |
System.out.print(" " + node.value); | |
} | |
} | |
public void traverseLevelOrder() { | |
if (root == null) { | |
return; | |
} | |
Queue<Node> nodes = new LinkedList<>(); | |
nodes.add(root); | |
while (!nodes.isEmpty()) { | |
Node node = nodes.remove(); | |
System.out.print(" " + node.value); | |
if (node.left != null) { | |
nodes.add(node.left); | |
} | |
if (node.left != null) { | |
nodes.add(node.right); | |
} | |
} | |
} | |
public void traverseInOrderWithoutRecursion() { | |
Stack<Node> stack = new Stack<Node>(); | |
Node current = root; | |
stack.push(root); | |
while(! stack.isEmpty()) { | |
while(current.left != null) { | |
current = current.left; | |
stack.push(current); | |
} | |
current = stack.pop(); | |
System.out.print(" " + current.value); | |
if(current.right != null) { | |
current = current.right; | |
stack.push(current); | |
} | |
} | |
} | |
public void traversePreOrderWithoutRecursion() { | |
Stack<Node> stack = new Stack<Node>(); | |
Node current = root; | |
stack.push(root); | |
while(! stack.isEmpty()) { | |
current = stack.pop(); | |
System.out.print(" " + current.value); | |
if(current.right != null) | |
stack.push(current.right); | |
if(current.left != null) | |
stack.push(current.left); | |
} | |
} | |
public void traversePostOrderWithoutRecursion() { | |
Stack<Node> stack = new Stack<Node>(); | |
Node prev = root; | |
Node current = root; | |
stack.push(root); | |
while (!stack.isEmpty()) { | |
current = stack.peek(); | |
boolean hasChild = (current.left != null || current.right != null); | |
boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); | |
if (!hasChild || isPrevLastChild) { | |
current = stack.pop(); | |
System.out.print(" " + current.value); | |
prev = current; | |
} else { | |
if (current.right != null) { | |
stack.push(current.right); | |
} | |
if (current.left != null) { | |
stack.push(current.left); | |
} | |
} | |
} | |
} | |
class Node { | |
int value; | |
Node left; | |
Node right; | |
Node(int value) { | |
this.value = value; | |
right = null; | |
left = null; | |
} | |
} | |
} | |
//////////// | |
// src: https://github.com/eugenp/tutorials/blob/5b5733239c06b595649324d744e97c6a2dc97d68/data-structures/src/test/java/com/baeldung/tree/BinaryTreeUnitTest.java | |
import static org.junit.Assert.assertEquals; | |
import static org.junit.Assert.assertFalse; | |
import static org.junit.Assert.assertTrue; | |
import org.junit.Test; | |
public class BinaryTreeUnitTest { | |
@Test | |
public void givenABinaryTree_WhenAddingElements_ThenTreeNotEmpty() { | |
BinaryTree bt = createBinaryTree(); | |
assertTrue(!bt.isEmpty()); | |
} | |
@Test | |
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() { | |
BinaryTree bt = createBinaryTree(); | |
assertTrue(bt.containsNode(6)); | |
assertTrue(bt.containsNode(4)); | |
assertFalse(bt.containsNode(1)); | |
} | |
@Test | |
public void givenABinaryTree_WhenAddingExistingElement_ThenElementIsNotAdded() { | |
BinaryTree bt = createBinaryTree(); | |
int initialSize = bt.getSize(); | |
assertTrue(bt.containsNode(3)); | |
bt.add(3); | |
assertEquals(initialSize, bt.getSize()); | |
} | |
@Test | |
public void givenABinaryTree_WhenLookingForNonExistingElement_ThenReturnsFalse() { | |
BinaryTree bt = createBinaryTree(); | |
assertFalse(bt.containsNode(99)); | |
} | |
@Test | |
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() { | |
BinaryTree bt = createBinaryTree(); | |
assertTrue(bt.containsNode(9)); | |
bt.delete(9); | |
assertFalse(bt.containsNode(9)); | |
} | |
@Test | |
public void givenABinaryTree_WhenDeletingNonExistingElement_ThenTreeDoesNotDelete() { | |
BinaryTree bt = createBinaryTree(); | |
int initialSize = bt.getSize(); | |
assertFalse(bt.containsNode(99)); | |
bt.delete(99); | |
assertFalse(bt.containsNode(99)); | |
assertEquals(initialSize, bt.getSize()); | |
} | |
@Test | |
public void it_deletes_the_root() { | |
int value = 12; | |
BinaryTree bt = new BinaryTree(); | |
bt.add(value); | |
assertTrue(bt.containsNode(value)); | |
bt.delete(value); | |
assertFalse(bt.containsNode(value)); | |
} | |
@Test | |
public void givenABinaryTree_WhenTraversingInOrder_ThenPrintValues() { | |
BinaryTree bt = createBinaryTree(); | |
bt.traverseInOrder(bt.root); | |
System.out.println(); | |
bt.traverseInOrderWithoutRecursion(); | |
} | |
@Test | |
public void givenABinaryTree_WhenTraversingPreOrder_ThenPrintValues() { | |
BinaryTree bt = createBinaryTree(); | |
bt.traversePreOrder(bt.root); | |
System.out.println(); | |
bt.traversePreOrderWithoutRecursion(); | |
} | |
@Test | |
public void givenABinaryTree_WhenTraversingPostOrder_ThenPrintValues() { | |
BinaryTree bt = createBinaryTree(); | |
bt.traversePostOrder(bt.root); | |
System.out.println(); | |
bt.traversePostOrderWithoutRecursion(); | |
} | |
@Test | |
public void givenABinaryTree_WhenTraversingLevelOrder_ThenPrintValues() { | |
BinaryTree bt = createBinaryTree(); | |
bt.traverseLevelOrder(); | |
} | |
private BinaryTree createBinaryTree() { | |
BinaryTree bt = new BinaryTree(); | |
bt.add(6); | |
bt.add(4); | |
bt.add(8); | |
bt.add(3); | |
bt.add(5); | |
bt.add(7); | |
bt.add(9); | |
return bt; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment