Matt Ryan

Posted on

# Day 47: Binary Search Tree

Constructor:

``````    public BinarySearchTree() {
root = null;
}
``````

Check to see if tree is empty:

``````    public boolean isEmpty() {
return root == null;
}
``````

Insert data:

``````    public void insert(int data) {
root = insert(root, data);
}
``````

Insert data recursively:

``````    private BSTNode insert(BSTNode node, int data) {
if (node == null) {
node = new BSTNode(data);
} else if (data <= node.getData()) {
node.left = insert(node.left, data);
} else {
node.right = insert(node.right, data);
}
return node;
}
``````

Delete data:

``````    public void delete(int k) {
if (isEmpty()) {
System.out.println("Tree Empty");
} else if (search(k) == false) {
System.out.println("Sorry " + k + " is not present");
} else {
root = delete(root, k);
System.out.println(k + " deleted from the tree");
}
}

private BSTNode delete(BSTNode root, int k) {
BSTNode p, p2, n;
if (root.getData() == k) {
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null) {
return null;
} else if (lt == null) {
p = rt;
return p;
} else if (rt == null) {
p = lt;
return p;
} else {
p2 = rt;
p = rt;
while (p.getLeft() != null) {
p = p.getLeft();
}
p.setLeft(lt);
return p2;
}
}
if (k < root.getData()) {
n = delete(root.getLeft(), k);
root.setLeft(n);
} else {
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
``````

Count the nodes:

``````    public int countNodes() {
return countNodes(root);
}
``````

Count the nodes recursively:

``````    private int countNodes(BSTNode r) {
if (r == null) {
return 0;
} else {
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
``````

Search the tree:

``````    public boolean search(int val) {
return search(root, val);
}
``````

Search the tree recursively:

``````    private boolean search(BSTNode r, int val) {
boolean found = false;
while ((r != null) && !found) {
int rval = r.getData();
if (val < rval) {
r = r.getLeft();
} else if (val > rval) {
r = r.getRight();
} else {
found = true;
break;
}
found = search(r, val);
}
return found;
}
``````

Tree Traversals:

Inorder traversal

``````    public List<BSTNode> inorder() {
List<BSTNode> walk = new ArrayList<>();
inorder(root, walk);
return walk;
}

private void inorder(BSTNode r, List<BSTNode> walk) {
if (r != null) {
inorder(r.getLeft(), walk);
System.out.print(r.getData() + " ");
inorder(r.getRight(), walk);
}
}
``````

Preorder

``````    public List preorder() {
List<BSTNode> walk = new ArrayList<>();
preorder(root, walk);
return walk;
}

private void preorder(BSTNode r, List<BSTNode> walk) {
if (r != null) {
System.out.print(r.getData() + " ");
preorder(r.getLeft(), walk);
preorder(r.getRight(), walk);
}
}
``````

Postorder

``````    public List<BSTNode> postorder() {
List<BSTNode> walk = new ArrayList<>();

postorder(root, walk);
return walk;
}

private void postorder(BSTNode r, List<BSTNode> walk) {
if (r != null) {
postorder(r.getLeft(), walk);
postorder(r.getRight(), walk);
System.out.print(r.getData() + " ");