BST.JAVA //sample implementation of a BST class BST { Node root; //reference to
ID: 3730514 • Letter: B
Question
BST.JAVA
//sample implementation of a BST
class BST {
Node root; //reference to root of the binary search tree
public BST() {
root = null;
}
//iterative insert
public void insert(int val) {
Node newNode,prev,curr;
boolean done = false;
prev = null;
curr = root;
newNode = new Node(val,null,null);
if (root == null) {
root = newNode;
}
else {
while (curr != null) {
prev = curr;
if (val < curr.key)
curr = curr.left;
else
curr = curr.right;
}
if (val < prev.key)
prev.left = newNode;
else
prev.right = newNode;
}
}
//recursive insert public drive method
public void insertR(int val) {
Node newNode;
if (root == null) {
root = new Node(val,null,null);
}
else {
insertR(null,root,val);
}
}
//recursive insert private helper method.
//this method does the actual insertion into a non-empty tree
private void insertR(Node prev, Node curr, int val) {
//prev-reference to previous node being considered.
//curr-reference to current node being considered.
//val - value to insert.
Node newNode;
if (curr == null) { //base case
newNode = new Node(val,null,null);
if (val < prev.key )
prev.left = newNode;
else
prev.right = newNode;
} //recursive case
else {
if (val < curr.key)
insertR(curr,curr.left,val);
else
insertR(curr,curr.right,val);
}
}
//iterative search
public boolean search(int key) {
Node curr=root;
boolean result = false;
while (curr !=null) {
if (curr.key == key) {
result = true;
break;
}
else if (key < curr.key)
curr = curr.left;
else
curr = curr.right;
}
return result;
}
//recursive search
public boolean searchR(int key) { //driver method
return searchR(key,root);
}
//this method does the actual recursive searching.
private boolean searchR(int key, Node curr) {
boolean result = false;
if (curr !=null) {
if (curr.key == key)
result = true;
else if (key < curr.key)
result = searchR(key,curr.left);
else
result = searchR(key,curr.right);
}
return result;
}
//inorder traversal (recursive)
private void inorder(Node curr) {
if (curr != null) {
inorder(curr.left);
curr.print();
inorder(curr.right);
}
}
public void inorder() {
inorder(root);
}
class Node {
int key;
Node left;
Node right;
public Node(int val, Node l, Node r) {
key = val;
left = l;
right = r;
}
public void print() {
System.out.println(key);
}
}
private Node findNode(int val) {
Node curr;
curr = root;
while (curr != null) {
if (curr.key == val)
break;
}
return curr;
}
private void easyDelete(Node delNode, Node delParent, Node delChild) {
//delNode-Node to be deleted
//delParent-parent of delNode
//delChild-child of delNode
if (delParent == null) { //deleting root node
root = delChild;
}
else { //delNode is not root
if (delNode == delParent.left)
delParent.left = delChild;
else
delParent.right = delChild;
}
}
private void twoChildrenDelete(Node curr) {
Node is, isParent; //inorder successor and inorder successor's parent
is = curr.right;
isParent = curr;
while (is.left != null) { //find inorder successor to curr.
isParent = is;
is = is.left;
}
curr.key = is.key; //put inorder sucessor's value into node curr.
easyDelete(is,isParent,is.right); //delete inorder successor node, which has no left child.
}
public void delete(int val) {
Node curr = root;
Node prev = null;
while (curr != null && curr.key != val) {
prev = curr;
if (val < curr.key)
curr = curr.left;
else
curr = curr.right;
}
if (curr != null) { //key found
if (curr.left == null)
easyDelete(curr,prev, curr.right);
else if (curr.right == null)
easyDelete(curr,prev,curr.left);
else
twoChildrenDelete(curr);
}
}
}
Explanation / Answer
To check binary tree is height-balanced or not
A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced.
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.
The above height-balancing scheme is used in AVL trees. The diagram below shows two trees, one of them is height-balanced and other is not. The second tree is not height-balanced because height of left subtree is 2 more than height of right subtree.
---------------------------------------------------------------------------------------------------------------------------
implementation :-
/* Java program to determine if binary tree is
height balanced or not */
/* A binary tree node has data, pointer to left child,
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
// A wrapper class used to modify height across
// recursive calls.
class Height
{
int height = 0;
}
class BinaryTree {
Node root;
/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node root, Height height)
{
/* If tree is empty then return true */
if (root == null)
{
height.height = 0;
return true;
}
/* Get heights of left and right sub trees */
Height lheight = new Height(), rheight = new Height();
boolean l = isBalanced(root.left, lheight);
boolean r = isBalanced(root.right, rheight);
int lh = lheight.height, rh = rheight.height;
/* Height of current node is max of heights of
left and right subtrees plus 1*/
height.height = (lh > rh? lh: rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if ((lh - rh >= 2) ||
(rh - lh >= 2))
return false;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else return l && r;
}
/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.left), height(node.right));
}
public static void main(String args[])
{
Height height = new Height();
/* Constructed binary tree is
1
/
2 3
/ /
4 5 6
/
7 */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(6);
tree.root.left.left.left = new Node(7);
if (tree.isBalanced(tree.root, height))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
------------------------------------------------------------------------------------------------------------------
/**
* to merge the 2 BST follow the below steps
* 1. Covert the BSTs to sorted linked list (using inorder traversal, Time O(m+n))
* 2. Merge this two sorted linked lists to a single list (same as merge portion of merge sort, Time O(m+n))
* 3. Convert sorted linked list to balanced BST (this can be done in place with O(m+n) time)
*/
import java.util.ArrayList;
import java.util.List;
public class MergeTwoBST {
class TreeNode {
private int value;
private TreeNode leftNode;
private TreeNode rightNode;
public TreeNode(int value) {
super();
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
}
public static TreeNode mergeBSTToFormBalancedTree(TreeNode tree1, TreeNode tree2){
if(tree1 != null && tree2 != null){
List<Integer> sortedList1 = new ArrayList<Integer>();
List<Integer> sortedList2 = new ArrayList<Integer>();
getSortedList(tree1, sortedList1);
getSortedList(tree2, sortedList2);
List<Integer> sortedList3 = merge(sortedList1, sortedList2);
return createTree(sortedList3, 0, sortedList3.size() - 1);
}
else if(tree1 != null){
return tree1;
}
else if(tree2 != null){
return tree2;
}
return null;
}
// left, root, right( INORDER TRAVERSAL GIVES SORTED ORDER)
private static void getSortedList(TreeNode node, List<Integer> sortedList){
if(node != null){
getSortedList(node.getLeftNode(), sortedList);
sortedList.add(node.getValue());
getSortedList(node.getRightNode(), sortedList);
}
}
private static List<Integer> merge(List<Integer> sortedList1, List<Integer> sortedList2){
List<Integer> mergeList = new ArrayList<Integer>(sortedList1.size() + sortedList2.size());
int index1 = 0, index2 = 0;
while(index1 < sortedList1.size() && index2 < sortedList2.size()){
if(sortedList1.get(index1) <= sortedList2.get(index2)){
mergeList.add(sortedList1.get(index1));
index1++;
} else {
mergeList.add(sortedList2.get(index2));
index2++;
}
}
while(index1 < sortedList1.size()){
mergeList.add(sortedList1.get(index1));
index1++;
}
while(index2 < sortedList2.size()){
mergeList.add(sortedList2.get(index2));
index2++;
}
return mergeList;
}
// Create Tree using array
private static TreeNode createTree(List<Integer> data, int begin, int end) {
if (begin > end) {
return null;
}
if (begin == end) {
return new TreeNode(data.get(begin));
}
int size = end - begin + 1;
int lSize = (size - 1) >> 1;
TreeNode parent = new TreeNode(data.get(begin + lSize));
parent.setLeftNode(createTree(data, begin, begin + lSize - 1));
parent.setRightNode(createTree(data, begin + lSize + 1, end));
return parent;
}
public static void printLevelWiseTree(List<TreeNode> nodes) {
if(nodes == null || nodes.isEmpty()){
return;
}
else{
List<TreeNode> next = new ArrayList<TreeNode>();
for(TreeNode node : nodes) {
System.out.print(node.getValue()+" ");
if(node.getLeftNode() != null){
next.add(node.getLeftNode());
}
if(node.getRightNode() != null){
next.add(node.getRightNode());
}
}
System.out.println();
printLevelWiseTree(next);
}
}
public static void main(String[] args) {
TreeNode tree1 = new TreeNode(90);
tree1.setLeftNode(new TreeNode(70));
tree1.setRightNode(new TreeNode(110));
TreeNode tree2 = new TreeNode(60);
tree2.setLeftNode(new TreeNode(5));
tree2.setRightNode(new TreeNode(800));
TreeNode balancedTree = mergeBSTToFormBalancedTree(tree1, tree2);
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(balancedTree);
printLevelWiseTree(list);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.